概要

\(N\) 個のバス停と \(M\) 個のバス路線がある街で、バス停 \(S\) から \(T\) へ向かうための最小の乗車回数を求める問題です。各路線には複数のバス停が含まれており、同じ路線内であればどのバス停間でも 1 回の乗車で移動できます。

考察

素朴なグラフ構築の問題点

この問題を「バス停を頂点、同じ路線で結ばれているバス停間に辺を張る」というグラフとして考えると、1つの路線に \(K\) 個のバス停がある場合、その路線内だけで \(K(K-1)/2\) 本の辺が必要になります。 制約では \(\sum K_i \leq 5 \times 10^5\) ですが、例えば 1 つの路線に全バス停が含まれる場合、辺の数が \(O(N^2)\) に達してしまい、実行時間制限（TLE）やメモリ制限（MLE）を超えてしまいます。

路線を「頂点」とみなす工夫

そこで、「バス停」だけでなく「バス路線」もグラフの頂点として扱うという工夫をします。 具体的には、以下の \(N + M\) 個の頂点を持つグラフを構築します。 - バス停を表す頂点： \(1, 2, \dots, N\) - バス路線を表す頂点： \(N+1, N+2, \dots, N+M\)

そして、バス路線 \(i\) がバス停 \(u\) を通るなら、「バス停 \(u\)」と「バス路線 \(N+i\)」の間に辺を張ります。 この工夫により、辺の総数は \(\sum K_i\) 本となり、制約内で十分に扱えるサイズになります。

アルゴリズム

この構築したグラフ上で、幅優先探索（BFS）を用いて最短経路を求めます。

1. 二部グラフの構築: バス停 \(u\) が路線 \(i\) に含まれるとき、無向辺 \((u, N+i)\) を追加します。

2. BFSの実行: バス停 \(S\) を始点として、各頂点への最短距離 dist を計算します。

   • 初期状態: dist[S] = 0、それ以外の頂点は -1（未訪問）。
   • キューに \(S\) を入れて探索開始。

3. 答えの計算: このグラフにおける移動は必ず「バス停 \(\to\) 路線 \(\to\) バス停 \(\to\) 路線 \(\dots\)」という交互の移動になります。

   • バス停 \(S\) からある路線 \(i\) へ移動する（dist が 1 増える）ことは、「その路線に乗る」ことに相当します。
   • その路線 \(i\) から別のバス停 \(v\) へ移動する（さらに dist が 1 増える）ことは、「その路線から降りる」ことに相当します。

   つまり、バス停 \(S\) からバス停 \(T\) までの最短距離が \(D\) であるとき、実際の乗車回数は \(D / 2\) 回となります。

計算量

• 時間計算量: \(O(N + M + \sum K_i)\)
  • グラフの頂点数は \(N+M\)、辺の数は \(\sum K_i\) です。BFSは各頂点と各辺を定数回ずつ走査するため、線形時間で動作します。
• 空間計算量: \(O(N + M + \sum K_i)\)
  • 隣接リストおよび距離配列を保持するために必要なメモリ量です。

実装のポイント

• 高速な入出力: Pythonの場合、入力行数が多いため sys.stdin.read().split() などを使って一括で読み込むと高速です。

• 目的地の判定: BFSの途中で目的地 \(T\) に到達した瞬間に dist[T] // 2 を出力して終了することで、わずかに高速化できます。最後まで探索しても \(T\) に到達できない場合は -1 を出力します。

  ソースコード

import sys
from collections import deque

def solve():
    # 入力をすべて読み込み、スペース区切りで分割してリストにする（高速化のため）
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 基本情報の取得
    # N: バス停の数, M: 路線の数, S: 出発バス停, T: 目的バス停
    N = int(input_data[0])
    M = int(input_data[1])
    S = int(input_data[2])
    T = int(input_data[3])
    
    # 二部グラフを構築する
    # バス停をノード 1 ～ N、バス路線をノード N+1 ～ N+M とする。
    # バス停 u が路線 v に含まれる場合、ノード u とノード N+v の間に辺を張る。
    adj = [[] for _ in range(N + M + 1)]
    
    ptr = 4
    for i in range(1, M + 1):
        K = int(input_data[ptr])
        ptr += 1
        route_node = N + i
        for _ in range(K):
            stop_node = int(input_data[ptr])
            ptr += 1
            adj[stop_node].append(route_node)
            adj[route_node].append(stop_node)
            
    # 幅優先探索 (BFS) を用いて、バス停 S から各ノードへの最短距離を求める
    # dist[i] はノード S からノード i までの二部グラフ上の距離
    dist = [-1] * (N + M + 1)
    dist[S] = 0
    queue = deque([S])
    
    while queue:
        u = queue.popleft()
        
        # 目的地 T に到達した場合
        if u == T:
            # 二部グラフ上の距離 2 (バス停 -> 路線 -> バス停) が乗車 1 回分に相当する
            print(dist[u] // 2)
            return
        
        # 隣接するノードを探索
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                queue.append(v)
                
    # 目的地 T に到達不可能な場合
    print("-1")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。