#!/usr/bin/python3
import sys
# Graph representation: adjacency list Adj[u] = [(v1,c1),(v2,c2),...]
# means edge (u,v1) with cost c1, edge (u,v2) with cost c2, etc.
Adj = []
Idx = {} # Idx: node name --> node index in Adj
Name = [] # Name[v] is the name of node v
# Utility function to add a node u to the graph. u is the node name.
def add_vertex(u):
global V_name, Idx, Adj
if u in Idx:
ui = Idx[u]
else:
ui = len(Adj)
Idx[u] = ui
Adj.append([])
Name.append(u)
return ui
# Read an undirected graph from the standard input. Input format: one
# edge per line. Line format: u v c(u,v), where u and v are strings,
# and c(u,v) is a number representing the cost of edge (u,v)
#
# E.g.:
# A B 10
# B C 5.2
# ...
for l in sys.stdin:
u, v, c = l.strip().split()
u = add_vertex(u)
v = add_vertex(v)
c = float(c)
Adj[u].append((v,c))
Adj[v].append((u,c))
def dijkstra(G,src): # G: adjacency list, src: source node
n = len(G) # n: number of vertices in G
D = [None]*n # D[v]: best known distance from src to v
P = [None]*n # P[v] = x means that x is the next-hop towards u
Q = [None]*n # queue of discovered nodes whose distance
Q_head = 0 # isn't yet finalized
Q_tail = 0
D[src] = 0.0 # start up the algorithm from the source node
Q[Q_tail] = src
Q_tail = Q_tail + 1
N = [False]*n # N[v] == True ==> v's distance from src is finalized
while Q_head < Q_tail:
# find the least-cost path extension: extract node u from Q
# such that D[u] is minimal
for i in range(Q_head + 1, Q_tail):
if D[Q[i]] < D[Q[Q_head]]:
Q[i], Q[Q_head] = Q[Q_head], Q[i]
u = Q[Q_head]
Q_head = Q_head + 1
N[u] = True # node u is settled
for v, c in G[u]: # for every edge u --> v with cost c
if N[v] == False:
if D[v] == None or D[v] > D[u] + c:
if D[v] == None:
Q[Q_tail] = v
Q_tail = Q_tail + 1
D[v] = D[u] + c
P[v] = u
return P, D # return "previous" and "distance" vectors
if len(sys.argv) > 1: # read the name of the starting node
src = Idx[sys.argv[1]] # from the first command-line argument,
else: # or start from the first node
src = 0
P,D = dijkstra(Adj, src)
for u in range(len(Adj)):
print(Name[u], D[u], P[u])