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

# Untitled

a guest Dec 13th, 2018 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. def dijkstra(g, start, finish, glasses):
2.     used = {start}
3.     dist = [10 ** 10] * (cv + 1)
4.     dist[start] = 0
5.     while len(used) != cv and finish not in used:
6.         minE = 10 ** 10
7.         thisV = -1
8.         for u in used:
9.             for v in g[u]:
10.                 if v[0] not in used:
11.                     if dist[u] + v[1] <= minE and v[2] >= glasses:
12.                             minE = dist[u] + v[1]
13.                             thisV = v[0]
14.         if thisV == -1:
15.             break
17.         dist[thisV] = minE
18.     if dist[finish] > 1440:
19.         return False
20.     else:
21.         return True
22.
23.
24. def binSearch(g, start, finish):
25.     l = 0
26.     r = 10000000
27.     m = 0
28.     while l != r:
29.         m = (l+r+1) // 2
30.         if dijkstra(g, start, finish, m):
31.             l = m
32.         else:
33.             r = m - 1
34.     return r
35.
36.
37. cv, ce = map(int, input().split())
38. start, finish = 1, cv
39. maxInt = 10 ** 10
40. g = [[] for i in range(cv+1)]
41. for i in range(ce):
42.     tempU, tempF, time, weight = map(int, input().split())
43.     weight = (weight - 3 * 10 ** 6) // 100
44.     if weight > 0:
45.         g[tempU].append([tempF, time, weight])
46. print(binSearch(g, start, finish))
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