正しくない実装。入力によっては正答を返さないし、そもそも最長経路問題にダイクストラ法は上手くいかない。
def dijk(s):
global d, prev
d = [0] * V
used = [False] * V
prev = [-1] * V
d[s] = 0
while True:
v = -1
for u in range(V):
if v!=-1 and cost[v][u] == INF: continue
if not used[u] and (v==-1 or d[u] > d[v]): v = u
if v == -1: break
used[v] = True
for u in range(V):
if cost[v][u] == INF: continue
if d[u] < d[v] + cost[v][u]:
d[u] = d[v] + cost[v][u]
prev[u] = v
def get_path(t):
path = []
while t != -1:
path.append(chr(ord('A')+t))
t = prev[t]
return ' -> '.join(path[::-1])
V, E = map(int, input('input:\n').split())
INF = 987654321
cost = [ [ INF for _ in range(V+1) ] for _ in range(V+1) ]
for _ in range(E):
a, b, c = input().split()
a = ord(a) - ord('A')
b = ord(b) - ord('A')
cost[a][b] = int(c)
dijk(0)
print(get_path(V-1))
print(d[V-1])
3 2 A C 1 B C 2
# 正答は A -> C で 1。 B -> C # Aが出発点にならない 2
5 5 A D 1 D B 100 D C 10 B C 1 C E 1
# 正答は A -> D -> B -> C -> E で 103。 A -> D -> C -> E 2