Submission #30845182

---

Source Code Expand

import heapq
n, m = map(int, input().split())
e = [[] for i in range(n)] # グラフの隣接リスト
for i in range(m):
    u, v, c = map(int, input().split())
    e[u].append([v, c]) # 行先の頂点とコストを一緒に持つ
dist = [10 ** 18] * n # 各頂点への最短距離 (確定または暫定値)
dist[0] = 0
q = [] # 最短距離確定済み頂点に隣接した頂点の集合
heapq.heappush(q, [0, 0])
while len(q) != 0: # 未確定の頂点が残っている間繰り返す
    d, v = heapq.heappop(q) # 暫定距離最小の頂点とその距離を取り出し削除
    if dist[v] != d:
        continue
    for u, c in e[v]: # 最短距離の暫定値を更新し，優先度付きキューに追加
        if dist[u] > d + c:
            dist[u] = d + c
            heapq.heappush(q, [d + c, u])
print(dist[n - 1])

Submission Info

Judge Result