Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def relax(u, v, l):
- dist[v] = min(dist[v], dist[u] + l)
- def dijkstra(st, fin):
- global n
- global dist
- global used
- dist[st] = 0
- for i in range(n):
- v = -1
- d = 10 ** 19
- for j in range(n):
- if used[j] == -1 and dist[j] < d:
- d = dist[j]
- v = j
- if v == -1:
- break
- used[v] = 1
- for elem in gr[v]:
- relax(v, elem[0], elem[1])
- if used[fin] == -1:
- return -1
- else:
- return dist[fin]
- n, st, fin = map(int, input().split())
- st -= 1
- fin -= 1
- matrix = []
- gr = [[] * n for i in range(n)]
- for i in range(n):
- matrix.append(list(map(int, input().split())))
- for i in range(len(matrix)):
- for j in range(len(matrix)):
- if i != j and matrix[i][j] != -1:
- gr[i].append((j, matrix[i][j]))
- dist = [10 ** 19] * n
- used = [-1] * n
- print(dijkstra(st, fin))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement