Day 005-Q3 | ダイクストラ法

問題

N頂点M辺の重み付き有向グラフ。頂点1を始点として全頂点への最短距離を求めよ。到達不可能な頂点には -1。

入力形式

N M
u1 v1 w1
...
uM vM wM

制約

$2 \le N \le 2 \times 10^5$

$1 \le M \le 5 \times 10^5$

$1 \le w \le 10^9$（非負）

入出力例

入力例 1

出力例 1

ヒント (段階的開示)

ヒント1: 方向性

重みが非負整数 → ダイクストラ法。O((V+E) log V)。

ヒント2: アプローチ

dist を inf 初期化 → ヒープから最小コスト頂点取り出し → 隣接緩和 → 確定済みはスキップ。

ヒント3: 誘導

import heapq
INF = float('inf')
dist = [INF] * (N + 1)
dist[1] = 0
pq = [(0, 1)]
while pq:
    d, v = heapq.heappop(pq)
    if d > dist[v]: continue
    for u, w in graph[v]:
        nd = d + w
        if nd < dist[u]:
            dist[u] = nd
            heapq.heappush(pq, (nd, u))

模範解答 (Python)

import sys
import heapq
input = sys.stdin.readline

def dijkstra(start, N, graph):
    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, v = heapq.heappop(pq)
        if d > dist[v]:
            continue
        for u, w in graph[v]:
            nd = d + w
            if nd < dist[u]:
                dist[u] = nd
                heapq.heappush(pq, (nd, u))
    return dist

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))

    dist = dijkstra(1, N, graph)

    for i in range(1, N + 1):
        print(dist[i] if dist[i] != float('inf') else -1)

main()

Step-by-Step 解説

1隣接リスト構築
有向グラフなので graph[u].append((v, w)) のみ。

2ヒープ初期化
(コスト, 頂点) タプルで最小ヒープ。

3緩和ループ
最小コスト取り出し → 確定済みスキップ → 隣接緩和。

4負辺があるとき
ダイクストラは負辺不可。ベルマン-フォード（O(VE)）を使う。

計算量

ヒープ操作: $O(E \log V)$
全体: $O((V + E) \log V)$

よくあるミス

ミス	原因	正しい書き方
無向にしてしまう	両方向追加	有向なら片方向のみ
スキップ忘れ	古いエントリ重複処理	`if d > dist[v]: continue`
到達不可能を0出力	inf チェック忘れ	-1 に変換

Day 005-Q3 — ダイクストラ法

問題