python
def shortest_path(
start, goal, num_vertexes, edges,
INF=9223372036854775807, UNREACHABLE=-1):
distances = [INF] * num_vertexes
prev = [None] * num_vertexes
distances[start] = 0
queue = [(0, start)]
while queue:
d, frm = heappop(queue)
if distances[frm] < d:
# already know shorter path
continue
if frm == goal:
path = [goal]
p = goal
while p != start:
p = prev[p]
path.append(p)
path.reverse()
return d, path
for to in edges[frm]:
new_cost = distances[frm] + edges[frm][to]
if distances[to] > new_cost:
# found shorter path
distances[to] = new_cost
prev[to] = frm
heappush(queue, (distances[to], to))
return UNREACHABLE
https://judge.yosupo.jp/submission/28034
old version
- Shortest Path
- Submitted python
from collections import defaultdict
from heapq import *
# fast input
import sys
input = sys.stdin.buffer.readline
INF = sys.maxsize
num_vertexes, num_edges, start, goal = map(int, input().split())
edges = defaultdict(dict)
distances = [INF] * num_vertexes
distances[start] = 0
shortest_path = defaultdict(list)
shortest_path[start] = []
for i in range(num_edges):
a, b, c = map(int, input().split())
edges[a][b] = c
# edges[b][a] = c # if bidirectional
queue = [(0, start)]
while queue:
d, frm = heappop(queue)
if distances[frm] < d:
# already know shorter path
continue
if frm == goal: # goal
break
for to in edges[frm]:
if distances[to] > distances[frm] + edges[frm][to]:
# found shorter path
distances[to] = distances[frm] + edges[frm][to]
heappush(queue, (distances[to], to))
shortest_path[to] = (frm, to)
if distances[goal] == INF:
# unreachable
print(-1)
else:
path = []
cur = goal
while True:
frm, to = shortest_path[cur]
path.append((frm, to))
cur = frm
if frm == start:
break
path.reverse()
print(distances[goal], len(path))
for frm, to in path:
print(frm, to)
このコードの修正点
- 最短パスの表示が必要でない時にどこを捨てればいいかを明確にする
- パスを構成するエッジの数を出力しているが、エッジコストの和を出したい場合も多い