Day 093-Q1 — 01-BFS（0-1 BFS）

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる。各辺の重みは $0$ または $1$ である。頂点 $1$ から各頂点への最短距離を求めよ。到達不可能な場合は -1 を出力せよ。

入出力例

4 4
1 2 1
1 3 0
3 2 0
2 4 1

0
0
0
1

頂点2へは直接辺（重み1）より、1→3（重み0）→2（重み0）の方が短く距離0。頂点4へは2から重み1で距離1。

概念図

ヒント

from collections import deque
dist = [INF]*(n+1); dist[1] = 0
dq = deque([1])
while dq:
    u = dq.popleft()
    for v, w in graph[u]:
        nd = dist[u] + w
        if nd < dist[v]:
            dist[v] = nd
            if w == 0:
                dq.appendleft(v)
            else:
                dq.append(v)

模範解答

import sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1

    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(data[idx]); v = int(data[idx + 1]); w = int(data[idx + 2])
        idx += 3
        graph[u].append((v, w))

    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[1] = 0
    dq = deque([1])

    while dq:
        u = dq.popleft()
        for v, w in graph[u]:
            nd = dist[u] + w
            if nd < dist[v]:
                dist[v] = nd
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)

    out = []
    for i in range(1, n + 1):
        out.append(str(dist[i]) if dist[i] != INF else "-1")
    sys.stdout.write("\n".join(out) + "\n")


main()

計算量: 各頂点・各辺は高々定数回キューに出入りするため $O(N+M)$。

Step-by-Step 解説

Step 1: 入力受け取りと隣接リスト構築

(v, w) のペアを頂点ごとのリストに格納する。

Step 2: dist配列とdequeの初期化

dist[1] = 0 とし、deque([1]) からスタートする。キューには「距離昇順に並ぶことが保証された」頂点が入る。

Step 3: メインループ（重みに応じてappendleft / append）

重み0の遷移は先頭に入れて即座に処理対象にし、重み1の遷移は末尾に回すことで、通常のBFSキューの「距離昇順」の性質を保ったまま拡張できる。

Step 4: 出力

未到達（INFのまま）の頂点には -1 を出力する。

よくあるミス

次のステップ

• 発展: 辺重みが $0,1,\dots,K$（小さい定数）への拡張（バケットキュー / Dial's Algorithm）
• 発展: 「壁を最大K枚まで壊せる」問題への応用（01-BFSを層状に拡張）
• 次回予告: 01-Trie（ビットトライ木・XOR最大値ペア探索）

自己評価