daily pastebin goal
40%
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. OK, I Understand
 
Top