• API
• FAQ
• Tools
• Archive
daily pastebin goal
57%
SHARE
TWEET

# Untitled

a guest Dec 16th, 2018 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. def dijkstra(N, S, matrix):
2.     valid = [True] * (N + 1)
3.     weight = [1000000] * (N + 1)
4.     weight[S] = 0
5.     for i in range(1, N + 1):
6.         min_weight = 1000001
7.         ID_min_weight = -1
8.         for i in range(1, N + 1):
9.             if valid[i] and weight[i] < min_weight:
10.                 min_weight = weight[i]
11.                 ID_min_weight = i
12.         for i in lst[ID_min_weight]:
13.             if weight[ID_min_weight] <= i[1] and i[2] < weight[i[0]]:
14.                 weight[i[0]] = i[2]
15.         valid[ID_min_weight] = False
16.     return weight
17.
18.
19. n = int(input())
20. d, v = map(int, input().split())
21. r = int(input())
22. lst = [[] for i in range(n + 1)]
23. for i in range(r):
24.     v1, t1, v2, t2 = map(int, input().split())
25.     lst[v1].append([v2, t1, t2])
26. w = dijkstra(n, d, lst)
27. if w[v] == 1000000:
28.     print('-1')
29. else:
30.     print(w[v])
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top