knightL

Dijkstra

Dec 17th, 2020
1,030
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.51 KB | None | 0 0
  1. n,s,f = map(int, input().split())
  2. s-=1
  3. f-=1
  4.  
  5. INF = 1000000000
  6.  
  7. Dist = [ 0 ] *n
  8. for i in range(n):
  9.     Dist[i] = list ( map( int, input().split() ) )
  10.  
  11. d = [ INF ] * n
  12. u = [ False ] *n
  13. d[s] = 0
  14.  
  15. for i in range(n):
  16.     minv = -1
  17.     for j in range(n):
  18.         if not u[j] and (minv == -1 or d[minv] > d[j] ):
  19.             minv = j
  20.    
  21.     if d[minv] == INF:
  22.         break
  23.        
  24.     u[minv] = True
  25.     for j in range(n):
  26.         if Dist[minv][j] != -1:
  27.             d[j] = min ( d[j], d[minv] + Dist[minv][j] )
  28.        
  29. if d[f] == INF:
  30.     print(-1)
  31. else:
  32.     print(d[f])
  33.  
Advertisement
Add Comment
Please, Sign In to add comment