daily pastebin goal
62%
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 = [10001] * (N + 1)
  3.     time[1] = 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[0]] > time[index] + k[1] and total_weight <= k[2]:
  15.                 time[k[0]] = time[index] + k[1]
  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. OK, I Understand
 
Top