• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Nov 13th, 2018 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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, elem)
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))
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.

Top