Олимпиада по Информатике

Question

Олимпиада по Информатике

fff ggg Ученик (139), на голосовании 3 недели назад

E. Сон таксиста (30 баллов)
Ограничение времени 1 секунда
Ограничение памяти 64Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Одному таксисту приснился красочный сон. Во сне он живет и работает в некотором городе, где абсолютно все улицы с односторонним движением. Эти улицы устроены так, что невозможно проехать с какого-либо перекрестка так, чтобы вернуться обратно на этот же перекресток, то есть в дорожной сети города нет циклов.

Таким образом, если с перекрестка A можно попасть по направлению движения улиц на перекресток B, то люди вызывают такси, иначе их везет специальный муниципальный подземный транспорт за бесплатно.

В связи с такими странными на наш взгляд правилами, таксистам в этом городе разрешено законом везти пассажира по любому маршруту, не нарушающему направления движения. Все в этом городе привыкли к такой ситуации и абсолютно спокойно относятся к тому, что таксисты везут их самым длинным путем. Само собой, заработок таксиста за одну поездку прямо пропорционален длине поездки, для упрощения будем считать, что стоимость одного километра поездки составляет ровно один рубль.

Схема дорог города задана. Перекрестки города пронумерованы числами от 1 до n. Наш таксист в своем сне находится на перекрестке номер S. Напишите программу, которая подскажет ему, сколько он максимально сможет заработать, когда ему придет заказ от клиента. Так как он не знает куда попросит его везти клиент, нужно для каждого перекрестка от 1 до n указать максимальную стоимость добраться до этого перекрестка из пункта S на такси. Если по правилам на такси добраться из пункта S до какого-то перекрестка нельзя, вывести -1.

Формат ввода
Дорожная сеть задана следующим образом: в первой строке находятся два числа через пробел n и m — число перекрестков и число улиц в городе. 2 ≤ n, m ≤ 2 * 105.

В следующих m строках задана очередная односторонняя улица в виде трех чисел A, B, d через пробел, где A начало улицы, B — конец улицы и d — её длина. 1 ≤ A, B ≤ n, 1 ≤ d ≤ 109. Гарантируется, что в этой дорожной сети нет циклов. Некоторые пары перекрестков могут быть соединены двумя и более односторонними улицами. Дорожная сеть может быть не плоской за счет мостов и тоннелей.

В последней строке ввода содержится номер стартового перекрестка S. 1 ≤ S ≤ n.

Формат вывода
Вывести n чисел в одну строку через пробел. i-е число обозначает длину самого длинного пути с перекрестка номер S до перекрестка номер i. Если до перекрестка номер i от S нельзя доехать, не нарушая правила движения, вывести -1.

Пример
Ввод Вывод
10 20 7 -1 2 9 0 18 13
9 10 15
9 8 3
8 10 7
7 8 4
7 10 10
5 8 2
5 9 10
5 6 5
7 6 5
4 6 8
3 6 4
3 4 6
5 3 2
2 5 2
2 3 3
3 1 5
1 4 2
2 1 7
4 7 4
6 8 1
5

Answer 1

Семён Мельников Ученик (139) 1 месяц назад

пните когда ответ будет

AaacoB AaacМудрец (14175) 1 месяц назад

а меня пните, когда пройдет неделя и ответа не будет...

AaacoB Aaac, а вон есть внизу "ответ" от очередного дауна, раскидывающего повсюду бред нейросети.

Answer 2

 from collections import defaultdict 
import heapq 
 
def build_graph(edges): 
    graph = defaultdict(list) 
    for u, v, w in edges: 
        graph[u].append((v, w)) 
    return graph 
 
def longest_path(graph, start): 
    distances = {node: float('-inf') for node in graph} 
    distances[start] = 0 
    priority_queue = [(-distances[start], start)] 
 
    while priority_queue: 
        current_distance, current_node = heapq.heappop(priority_queue) 
        current_distance = -current_distance 
         
        if current_distance < distances[current_node]: 
            continue 
         
        for neighbor, weight in graph[current_node]: 
            distance = current_distance + weight 
             
            if distance > distances[neighbor]: 
                distances[neighbor] = distance 
                heapq.heappush(priority_queue, (-distance, neighbor)) 
 
    return distances 
 
edges = [ 
    (9, 10, 15), 
    (9, 8, 3), 
    (8, 10, 7), 
    (7, 8, 4), 
    (7, 10, 10), 
    (5, 8, 2), 
    (5, 9, 10), 
    (5, 6, 5), 
    (7, 6, 5), 
    (4, 6, 8), 
    (3, 6, 4), 
    (3, 4, 6), 
    (5, 3, 2), 
    (2, 5, 2), 
    (2, 3, 3), 
    (3,1 ,5), 
    (1 ,4 ,2), 
    (2 ,1 ,7), 
    (4 ,7 ,4), 
    (6 ,8 ,1) 
] 
 
graph = build_graph(edges) 
result = longest_path(graph, start=5) 
 
output = [result.get(i, -1) for i in range(1, max(graph.keys()) + 1)] 
print(" ".join(map(str, output)))