 # dijkstra_pq

Aug 9th, 2022
479
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from queue import PriorityQueue
2. from collections import deque
3.
4. class Edge:
5.     def __init__(self, source, destination, weight):
6.         self.source = source
7.         self.destination = destination
8.         self.weight = weight
9.
10.
11. edges = int(input())
12. graph = {}
13.
14. for _ in range(edges):
15.     source, destination, weight = [int(x) for x in input().split(', ')]
16.     if source not in graph:
17.         graph[source] = []
18.     if destination not in graph:
19.         graph[destination] = []
20.     graph[source].append(Edge(source, destination, weight))
21.
22. start = int(input())
23. target = int(input())
24. max_node = max(graph.keys())
25. distance = [float('inf')] * (max_node + 1)
26. parent = [None] * (max_node + 1)
27.
28. distance[start] = 0
29.
30. pq = PriorityQueue()
31. pq.put((0, start))
32.
33. while not pq.empty():
34.     min_dist, node = pq.get()
35.     if node == target:
36.         break
37.     for edge in graph[node]:
38.         new_distance = min_dist + edge.weight
39.         if new_distance < distance[edge.destination]:
40.             distance[edge.destination] = new_distance
41.             parent[edge.destination] = node
42.             pq.put((new_distance, edge.destination))
43.
44. if distance[target] == float('inf'):
45.     print('There is no such path.')
46. else:
47.     print(distance[target])
48.
49.     path = deque()
50.     node = target
51.     while node is not None:
52.         path.appendleft(node)
53.         node = parent[node]
54.     print(*path)