 # undefined_Bellman_Ford

Aug 9th, 2022 (edited)
737
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from collections import deque
2.
3.
4. def find_path(parent, node):
5.     result = deque()
6.     while node is not None:
7.         result.appendleft(node)
8.         node = parent[node]
9.     return result
10.
11.
12. nodes = int(input())
13. edges = int(input())
14.
15. graph = []
16.
17. for _ in range(edges):
18.     first, second, weight = [int(x) for x in input().split()]
19.     graph.append((first, second, weight))
20.
21. source = int(input())
22. destination = int(input())
23.
24. distance = [float('inf')] * (nodes + 1)
25. distance[source] = 0
26. parent = [None] * (nodes + 1)
27.
28. for _ in range(nodes - 1):
29.     for first, second, weight in graph:
30.         if distance[first] == float('inf'):
31.             continue
32.         new_distance = distance[first] + weight
33.         if new_distance < distance[second]:
34.             distance[second] = new_distance
35.             parent[second] = first
36.
37. for first, second, weight in graph:
38.     new_distance = distance[first] + weight
39.     if new_distance < distance[second]:
40.         print('Undefined')
41.         break
42. else:
43.     path = find_path(parent, destination)
44.     print(*path)
45.     print(distance[destination])