概要

\(N\) 個のバス停と \(M\) 本のバス路線がある街で、バス停 \(S\) からバス停 \(T\) へ行くために必要な最小乗車回数を求める問題です。

考察

素朴なアプローチとその問題点

最も直感的な方法は、「同じバス路線に属するバス停同士をすべて辺で結んだグラフ」を作り、BFS で最短距離を求めることです。しかし、バス路線 \(i\) に \(K_i\) 個のバス停があると、そのペア数は \(O(K_i^2)\) になります。全路線で合計すると辺数が非常に多くなり、TLE（時間超過）になる可能性があります。

重要な気づき：仮想ノードの導入

辺の数を減らすために、各バス路線を表す仮想ノードを導入します。

バス路線 \(i\) に対して仮想ノード \(R_i\) を作り、次のように辺を張ります：

• バス停 → 仮想ノード（コスト 0）：バス停からバス路線に「乗車」する操作（まだ乗っただけなので回数は増えない）
• 仮想ノード → バス停（コスト 1）：バス路線からバス停に「下車」する操作（1回の乗車が完了）

例えば、路線 \(i\) がバス停 \(\{1, 3, 5\}\) を通る場合：

バス停1 --0--> R_i --1--> バス停1
バス停3 --0--> R_i --1--> バス停3
バス停5 --0--> R_i --1--> バス停5

こうすると、「バス停1 → R_i → バス停5」のように、コスト \(0 + 1 = 1\) でバス停1からバス停5へ移動できます。これは「路線 \(i\) に1回乗った」ことに対応します。

辺の本数は各路線について \(2K_i\) 本なので、合計 \(O(\sum K_i)\) 本に抑えられます。

アルゴリズム

辺のコストが 0 または 1 の2種類しかないため、通常の BFS（すべての辺の重みが等しい場合）の代わりに 0-1 BFS を使います。

0-1 BFS は、両端キュー（deque）を使った BFS の変種です：

1. 距離配列 \(\mathrm{dist}\) を \(\infty\) で初期化し、\(\mathrm{dist}[S] = 0\) とする。
2. deque に \(S\) を入れる。
3. deque の先頭からノード \(u\) を取り出し、各隣接ノード \(v\) について：
   • コスト \(0\) の辺なら、\(v\) を deque の先頭に追加（優先的に処理）
   • コスト \(1\) の辺なら、\(v\) を deque の末尾に追加
4. \(\mathrm{dist}[T]\) が答え。\(\infty\) のままなら \(-1\) を出力。

これにより、Dijkstra法のような優先度付きキューを使わずとも、\(O(V + E)\) で最短距離を求められます。

計算量

\(K = \sum_{i=1}^{M} K_i\) とおくと：

• 時間計算量: \(O(N + M + K)\)
  • ノード数 \(N + M\)、辺数 \(2K\) のグラフ上で 0-1 BFS を行う
• 空間計算量: \(O(N + M + K)\)
  • 隣接リストと距離配列の格納に必要

実装のポイント

• ノード番号の割り当て：バス停を \(0, 1, \dots, N-1\)、仮想ノード（路線ノード）を \(N, N+1, \dots, N+M-1\) とすると管理しやすい。

• 0-1 BFS の正しい使い方：コスト 0 の辺は appendleft、コスト 1 の辺は append で deque に追加する。順序を間違えると最短距離が正しく求まらない。

• 早期終了：deque から \(T\) を取り出した時点で最短距離が確定しているため、即座に答えを出力して終了できる。

  ソースコード

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
    S = int(data[idx]) - 1; idx += 1
    T = int(data[idx]) - 1; idx += 1

    # Nodes 0..N-1: bus stops, Nodes N..N+M-1: virtual route nodes
    total = N + M
    adj = [[] for _ in range(total)]

    for i in range(M):
        K = int(data[idx]); idx += 1
        route_node = N + i
        for _ in range(K):
            a = int(data[idx]) - 1; idx += 1
            # stop -> route: weight 0 (boarding)
            adj[a].append((route_node, 0))
            # route -> stop: weight 1 (alighting = 1 ride)
            adj[route_node].append((a, 1))

    # 0-1 BFS
    INF = float('inf')
    dist = [INF] * total
    dist[S] = 0
    dq = deque([S])

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

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

main()

---

この解説は claude4.6opus-thinking によって生成されました。