提出 #74603969

---

ソースコード 拡げる

import heapq
import sys
input = sys.stdin.readline

N, M = map(int, input().split())

# adjacency list
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    u, v, c = map(int, input().split())
    graph[u].append((v, c))

# distance array
INF = 10**18
dist = [INF] * (N + 1)
dist[1] = 0

# min heap (distance, node)
pq = [(0, 1)]

while pq:
    d, node = heapq.heappop(pq)

    if d > dist[node]:
        continue

    for nxt, cost in graph[node]:
        new_dist = d + cost
        if new_dist < dist[nxt]:
            dist[nxt] = new_dist
            heapq.heappush(pq, (new_dist, nxt))

print(dist[N])

提出情報

ジャッジ結果