Advertisement
Guest User

Untitled

a guest
Dec 14th, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.79 KB | None | 0 0
  1. from queue import Queue
  2.  
  3.  
  4. def dijkstra(G):
  5. for i in range(len(matrix[G])):
  6. if matrix[G][i] >= 0:
  7. dist[i] = matrix[G][i]
  8. qeueu.put(i)
  9. dist[G] = 0
  10. while qeueu:
  11. first_el = qeueu.get()
  12. for i in range(len(matrix[first_el])):
  13. if matrix[first_el][i] > 0:
  14. if dist[i] > dist[first_el] + matrix[first_el][i]:
  15. dist[i] = dist[first_el] + matrix[first_el][i]
  16. qeueu.put(i)
  17.  
  18.  
  19. N, S, F = map(int, input().split())
  20. S -= 1
  21. F -= 1
  22. matrix = [list() for _ in range(N)]
  23. for i in range(N):
  24. matrix[i] = list(map(int, input().split()))
  25. dist = [10 ** 100] * N
  26. used = [False] * N
  27. qeueu = Queue()
  28. dijkstra(S)
  29. if dist[F] == 10 ** 100:
  30. print(-1)
  31. else:
  32. print(dist[F])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement