fork download
copy 
  1. class Node():
  2.   def __init__(self, name, value, pre = None):
  3.     self.name = name
  4.     self.value = value
  5.     self.pre = pre
  6.  
  7. def build_min_heap(list):
  8.   n = len(list)
  9.   for i in range(n//2):
  10.     min_heapify(list, i)
  11.   return list
  12.  
  13. def min_heapify(list, i):
  14.   n = len(list)
  15.   small = i
  16.   L = left(i)
  17.   R = right(i)
  18.  
  19.   if ( L < n) and ( list[small].value > list[L].value): 
  20.     small = L
  21.   if ( R < n) and ( list[small].value > list[R].value): 
  22.     small = R
  23.  
  24.   if ( small != i):
  25.     list[i], list[small] = list[small], list[i]
  26.     min_heapify(list, small)
  27.  
  28. def Extract_min(Q):
  29.   Q[0], Q[-1] = Q[-1], Q[0]
  30.   Small = Q.pop()
  31.   build_min_heap(Q)
  32.   return Small
  33.  
  34. def parent(i):
  35.   return (i-1) // 2
  36.  
  37. def left(i):
  38.   return i*2 + 1
  39.  
  40. def right(i):
  41.   return i*2 + 2
  42.  
  43. def dijkstra(G, W, s):
  44.   initialize(G,s)
  45.   S = []
  46.   Q = build_min_heap(G)
  47.   while (len(Q)>0):
  48.     u = Extract_min(Q)
  49.     S.append(u)
  50.     for i in Q:
  51.       if (adj(W, u, i) == True):
  52.         w = W[(u.name, i.name)]
  53.         relax(u, i, w)
  54.     Q = build_min_heap(Q)
  55.   return S
  56.  
  57. def initialize(G, s):
  58.   for i in G:
  59.     if ( i.name == s):
  60.       i.value = 0
  61.     else:
  62.       i.value = float("inf")
  63.  
  64. def relax(u, v, w):
  65.   if ( v.value > u.value + w):
  66.     v.value = u.value + w
  67.     v.pre = u
  68.  
  69. def adj(W, u, v):    
  70.   if ( (u.name, v.name) in W ):
  71.     return True
  72.   else:
  73.     return False
  74.  
  75. if __name__ == '__main__':
  76.   V = input().split(",")
  77.   G = []
  78.   for i in V:
  79.     G.append(Node(i, 0, None))  
  80.  
  81.   n = int(input())
  82.   W={}
  83.   for i in range(n):
  84.     edge = input().split(",")
  85.     W[(edge[0],edge[1])] = int(edge[2])
  86.  
  87.   End = dijkstra(G,W,G[0].name)
  88.  
  89.   answer = {}
  90.   for i in End:
  91.     answer[i.name] = i.value
  92.  
  93.   for i in V:
  94.     print(answer[i])
Success #stdin #stdout 0.03s 9132KB
comments (?)
stdin
copy 
A,B,C,D,E
10
A,B,10
A,C,5
B,C,2
B,D,1
C,B,3
C,D,9
C,E,2
D,E,4
E,A,7
E,D,6
stdout
copy 
0
8
5
9
7
https://ideone.com/4uzWDr
language:
Python 3 (python  3.9.5)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!