空入力でテストを出力。トポロジカルソートは実は自力実装しなくてもgraphlibにある。（今回は不使用。toposort_graphlibの部分。）
# graph は隣接リスト(辞書)で管理
from collections import namedtuple, deque, defaultdict
Node = namedtuple('Node' , ["v", "cost"])
s = input('input:\n').strip()
for _ in range(1):
if s == '':
# test data
V, E = 5, 5
graph = {
'A':[Node('D',1)],
'B':[Node('C',1)],
'C':[Node('E',1)],
'D':[Node('B',100), Node('C',10)],
'E':[]}
break
V, E = map(int, s.split())
graph = defaultdict(list)
for _ in range(E):
src, dst, cost = input().upper().split()
graph[src].append(Node(dst, int(cost)))
graph[dst] # default [] will be made when no entry
vertexes = sorted(graph.keys())
START = 'A'
END = vertexes[-1]
def toposort(graph): # 深さ優先探索（DFS）を使うタイプ
res = []
visited = dict((v, False) for v in vertexes)
is_start_found = False
stack = deque()
for v in vertexes:
if is_start_found: break
stack.append(v)
while stack:
u = stack.pop()
if not visited[u]: # 行きがけ
stack.append(u)
visited[u] = True
for node in graph[u]:
if visited[node.v]: continue
stack.append(node.v)
else: # 帰りがけ
res.append(u)
if u == START:
is_start_found = True
break
res.reverse()
return res
def toposort_graphlib(graph):
import graphlib
# graphlib 用の隣接辞書は先行ノード管理型なので矢の向きが逆
g = dict((v,[]) for v in graph.keys())
for src_v, src_list in graph.items():
for dst in src_list:
g[dst.v].append(src_v)
ts = graphlib.TopologicalSorter(g)
return tuple(ts.static_order())
topo_order = toposort(graph)
# DP
dists = dict((v, -1) for v in vertexes)
dists[START] = 0
prevs = dict((v, -1) for v in vertexes)
for v in topo_order:
if dists[v] == -1: continue # STARTと繋がっていない
for node in graph[v]:
if dists[node.v] < dists[v] + node.cost:
dists[node.v] = dists[v] + node.cost
prevs[node.v] = v
def get_path(t):
path = []
while t != -1:
path.append(t)
t = prevs[t]
path.reverse()
return path
print()
c_path = get_path(END)
print(' -> '.join(c_path))
print(dists[END])
# 簡易チャート
print()
topo_s = [v for v in topo_order if dists[v] != -1]
c_edges = [c_path[i: i+2] for i in range(len(c_path)-1)]
print(''.join(f"{v:<7}" for v in topo_s))
for v in topo_s:
src_i = topo_s.index(v)
for node in graph[v]:
dst_i = topo_s.index(node.v)
is_critical = [v, node.v] in c_edges
line_char = "*" if is_critical else "-"
line = f"{node.cost:{line_char}^{(dst_i-src_i)*7}}"
print(' '*7*src_i + line + '>')
A D B C E
***1***>
**100**>
------10------>
***1***>
***1***>
正しくない実装。入力によっては正答を返さないし、そもそも最長経路問題にダイクストラ法は上手くいかない。
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