Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Nov 13th, 2018 82 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  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[0], elem[1])
  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. OK, I Understand
 
Top