• API
• FAQ
• Tools
• Archive
SHARE
TWEET Untitled a guest Dec 16th, 2018 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. def dijkstra(m):
2.     time =  * (N + 1)
3.     time = 0
4.     valid = [True] * (N + 1)
5.     total_weight = 100 * m + 3000000
6.     for j in range(N):
7.         index = -1
8.         minW = 10001
9.         for i in range(1, N + 1):
10.             if valid[i] and time[i] < minW:
11.                 minW = time[i]
12.                 index = i
13.         for k in matr[index]:
14.             if time[k] > time[index] + k and total_weight <= k:
15.                 time[k] = time[index] + k
16.         valid[index] = False
17.     if time[-1] <= 1440:
18.         ans = 0
19.     else:
20.         ans = 1
21.     return ans
22.
23.
24. def binsearch():
25.     low = 0
26.     hi = 10000001
27.     mid = (low + hi) // 2
28.     while hi != low:
29.         mid = (low + hi) // 2
30.         res = dijkstra(mid)
31.         if res == 1:
32.             hi = mid
33.         else:
34.             low = mid
35.     return hi - 1
36.
37.
38. N, M = map(int, input().split())
39. if M != 0:
40.     matr = [[] for i in range(N + 1)]
41.     for i in range(1, M + 1):
42.         v1, v2, t, w = map(int, input().split())
43.         matr[v1].append([v2, t, w])
44.         matr[v2].append([v1, t, w])
45.     print(binsearch())
46. elif N == 1:
47.     print(10000000)
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