Advertisement
Guest User

Untitled

a guest
Dec 15th, 2018
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.81 KB | None | 0 0
  1. def D(g, n, s):
  2.     visited = [0] * n
  3.     distance = [101] * n
  4.     distance[s - 1] = 0
  5.     for i in range(n):
  6.         min = 102
  7.         u = 0
  8.         for j in range(n):
  9.             if visited[j] == 0 and distance[j] < min:
  10.                 min = distance[j]
  11.                 u = j
  12.         if distance[u] == 101:
  13.             return -1
  14.         else:
  15.             visited[u] = 1
  16.             for j in range(n):
  17.                 if g[u][j] >= 0:
  18.                     if distance[j] > distance[u] + g[u][j]:
  19.                         distance[j] = distance[u] + g[u][j]
  20.     return distance
  21.  
  22.  
  23. n, s, f = map(int, input().split())
  24. g = []
  25. for i in range(n):
  26.     l = list(map(int, input().split()))
  27.     g.append(l)
  28. distance = D(g, n, s)
  29. if distance[f - 1] == 101:
  30.     print(-1)
  31. else:
  32.     print(distance[f - 1])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement