Advertisement
Guest User

Untitled

a guest
Nov 13th, 2018
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.94 KB | None | 0 0
  1. def relax(u, v, l):
  2. dist[v] = min(dist[v], dist[u] + l)
  3.  
  4.  
  5. def dijkstra(st, fin):
  6. global n
  7. global dist
  8. global used
  9. dist[st] = 0
  10. for i in range(n):
  11. v = -1
  12. d = 10 ** 19
  13. for j in range(n):
  14. if used[j] == -1 and dist[j] < d:
  15. d = dist[j]
  16. v = j
  17. if v == -1:
  18. break
  19.  
  20. used[v] = 1
  21. for elem in gr[v]:
  22. relax(v, elem[0], elem[1])
  23. if used[fin] == -1:
  24. return -1
  25. else:
  26. return dist[fin]
  27.  
  28.  
  29. n, st, fin = map(int, input().split())
  30. st -= 1
  31. fin -= 1
  32. matrix = []
  33. gr = [[] * n for i in range(n)]
  34. for i in range(n):
  35. matrix.append(list(map(int, input().split())))
  36. for i in range(len(matrix)):
  37. for j in range(len(matrix)):
  38. if i != j and matrix[i][j] != -1:
  39. gr[i].append((j, matrix[i][j]))
  40. dist = [10 ** 19] * n
  41. used = [-1] * n
  42. print(dijkstra(st, fin))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement