class Node(): def __init__(self, name, value, pre = None): self.name = name self.value = value self.pre = pre def build_min_heap(list): n = len(list) for i in range(n//2): min_heapify(list, i) return list def min_heapify(list, i): n = len(list) small = i L = left(i) R = right(i) if ( L < n) and ( list[small].value > list[L].value): small = L if ( R < n) and ( list[small].value > list[R].value): small = R if ( small != i): list[i], list[small] = list[small], list[i] min_heapify(list, small) def Extract_min(Q): Q[0], Q[-1] = Q[-1], Q[0] Small = Q.pop() build_min_heap(Q) return Small def parent(i): return (i-1) // 2 def left(i): return i*2 + 1 def right(i): return i*2 + 2 def dijkstra(G, W, s): initialize(G,s) S = [] Q = build_min_heap(G) while (len(Q)>0): u = Extract_min(Q) S.append(u) for i in Q: if (adj(W, u, i) == True): w = W[(u.name, i.name)] relax(u, i, w) Q = build_min_heap(Q) return S def initialize(G, s): for i in G: if ( i.name == s): i.value = 0 else: i.value = float("inf") def relax(u, v, w): if ( v.value > u.value + w): v.value = u.value + w v.pre = u def adj(W, u, v): if ( (u.name, v.name) in W ): return True else: return False if __name__ == '__main__': V = input().split(",") G = [] for i in V: G.append(Node(i, 0, None)) n = int(input()) W={} for i in range(n): edge = input().split(",") W[(edge[0],edge[1])] = int(edge[2]) End = dijkstra(G,W,G[0].name) answer = {} for i in End: answer[i.name] = i.value for i in V: print(answer[i])
A,B,C,D,E,F,G,H,I,J 50 A,D,3 A,F,3 A,G,6 A,J,7 B,A,2 B,E,5 B,H,7 C,H,1 D,A,5 D,B,7 D,E,2 D,F,3 D,G,7 D,H,7 D,J,3 E,A,3 E,B,1 E,C,5 E,D,6 E,F,4 E,H,7 E,I,5 E,J,6 F,A,6 F,C,1 F,D,2 F,E,3 F,G,2 F,H,6 F,I,5 F,J,4 G,B,1 G,C,5 G,D,5 G,E,6 G,H,5 G,I,6 H,B,2 H,C,6 H,D,6 H,G,3 H,I,7 I,A,6 I,D,6 I,F,3 I,G,4 I,H,2 I,J,5 J,D,7 J,H,1