Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def dijkstra(N, S, matrix):
- valid = [True] * (N + 1)
- weight = [1000000] * (N + 1)
- weight[S] = 0
- for i in range(1, N + 1):
- min_weight = 1000001
- ID_min_weight = -1
- for i in range(1, N + 1):
- if valid[i] and weight[i] < min_weight:
- min_weight = weight[i]
- ID_min_weight = i
- for i in lst[ID_min_weight]:
- if weight[ID_min_weight] <= i[1] and i[2] < weight[i[0]]:
- weight[i[0]] = i[2]
- valid[ID_min_weight] = False
- return weight
- n = int(input())
- d, v = map(int, input().split())
- r = int(input())
- lst = [[] for i in range(n + 1)]
- for i in range(r):
- v1, t1, v2, t2 = map(int, input().split())
- lst[v1].append([v2, t1, t2])
- w = dijkstra(n, d, lst)
- if w[v] == 1000000:
- print('-1')
- else:
- print(w[v])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement