Олимпиада по Информатике
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
пните когда ответ будет
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)))