【Python】有向グラフの最短経路に含まれる辺を列挙 - Qiita

from collections import deque,defaultdict # 頂点数:n # 辺の数:m n,m=map(int,input().split()) edge=defaultdict(list) for i in range(m): # 0-indexにする s,t=map(lambda x:int(x)-1,input().split()) # 遷移先の頂点と辺のindexを追加する edge[s].append((t,i)) INF=float('inf') # 頂点0からの距離 dist=[] # ひとつ前の頂点と辺のindex back=[(-1,-1)]*n def bfs(s): global dist,back dist=[INF]*n dist[s]=0 q=deque() q.appendleft(s) while len(q)>0: now=q.