daily pastebin goal
23%
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
  16.         used.add(thisV)
  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. OK, I Understand
 
Top