from heapq import heappush, heappopimport mathINF = 10 ** 18def dijkstra(s, n): # (始点, ノード数) dist = [INF] * n hq = [(0, s)] # (distance, node) dist[s] = 0 seen = [False] * n # ノードが確定済みかどうか while hq: v = heappop(hq)[1] # …