Day 005-Q2 | Phase 3 総復習

問題

N頂点M辺の重み付き無向グラフ。頂点1から頂点Nまでの最短距離を求めよ。重みは非負整数。BFSで解ける場合とDP（メモ化）で解ける場合の両方を考えよ。

入力形式

N M
u1 v1 w1
...
uM vM wM

制約

$2 \le N \le 10^4$

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

$0 \le w \le 10^9$

入出力例

入力例 1

出力例 1

1→2→3→4 のコスト 2+1+2=5

ヒント (段階的開示)

ヒント1: 方向性

重みが0/1ならBFS、一般非負整数ならダイクストラ。優先度付きキューを使う。

ヒント2: アプローチ

dist[v]を INF で初期化、小さい順に取り出して緩和する。

ヒント3: 誘導

import heapq
dist = [float('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]:
        if dist[v] + w < dist[u]:
            dist[u] = dist[v] + w
            heapq.heappush(pq, (dist[u], u))

模範解答 (Python)

import sys
import heapq
input = sys.stdin.readline

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))
        graph[v].append((u, w))

    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]:
            if dist[v] + w < dist[u]:
                dist[u] = dist[v] + w
                heapq.heappush(pq, (dist[u], u))

    ans = dist[N]
    print(ans if ans != INF else -1)

main()

Step-by-Step 解説

1グラフ構築
隣接リスト形式 graph[u] = [(v, w), ...]。無向なので両方向。

2優先度付きキューで最小コスト優先探索
heapq（最小ヒープ）から最小コスト頂点を取り出す。

3緩和（Relaxation）
dist[v] + w < dist[u] なら更新してキューに追加。

4Phase 3 アルゴリズム総まとめ
DFS, BFS, DP(1D/2D), Union-Find, 優先度付きキュー。

よくあるミス

ミス	原因	正しい書き方
古い値でスキップしない	同じ頂点が複数キューに	`if d > dist[v]: continue`
無向で片方向のみ	両方向追加忘れ	両方追加

Day 005-Q2 — Phase 3 総復習

問題