概要

各バス路線を 1 つの頂点とみなし、「同じバス停を共有する路線どうしは乗り換えできる」と考えると、最小乗車回数はこの路線グラフ上の最短距離として求められます。
ただし路線間の辺を素直に全部張ると重いので、バス停を介して BFS を行うのがポイントです。

考察

この問題では、1 回バスに乗ると「その路線が通る任意の別のバス停」へ移動できます。
つまり、いったん路線に乗れば、その路線上の全バス停に到達できると考えてよいです。

重要な気づき 1: 「バス停」より「路線」を状態にする

たとえば路線 \(i\) に乗っているなら、その路線上のどのバス停にも行けます。
そのため状態を「今どのバス停にいるか」で持つよりも、今どの路線に乗っているかで持つ方が自然です。

• 路線 \(i\) を使う = その路線に 1 回乗車する
• 同じバス停を共有する 2 路線の間では乗り換えできる

したがって、

• 出発点: \(S\) を通るすべての路線（最初の乗車なので距離 \(1\)）
• 目標: \(T\) を通るいずれかの路線に到達すること

とすれば、答えは「路線の乗り継ぎ回数」になります。

重要な気づき 2: 路線グラフを明示的に作ると重い

路線を頂点として、同じバス停を共有する路線同士に辺を張ることを考えます。
しかし、あるバス停を通る路線がたくさんあると、そのバス停だけで大量の辺ができます。

例えば、あるバス停を \(d\) 本の路線が通ると、その間には最大で \(O(d^2)\) 本の辺が必要です。
これを全バス停について行うと、最悪ではとても間に合いません。

重要な気づき 3: バス停を介して「必要になったときだけ」遷移する

そこで、

• 各路線がどのバス停を通るか
• 各バス停をどの路線が通るか

の 2 つだけ持っておき、BFS 中に必要になったときだけ遷移を調べます。

路線 \(r\) を BFS で取り出したら、その路線上の各バス停 stop を見て、
その stop を通る他の路線へ遷移すればよいです。

なぜ used_stop が必要か

同じバス停を何度も調べると無駄が大きくなります。
例えば 1 つのバス停を通る路線が多いと、そのバス停を通るたびに同じ路線一覧を見直してしまいます。

そこで各バス停について、

• そのバス停から他路線への展開を 最初の 1 回だけ 行う

ようにします。

BFS では距離の小さい順に探索するので、あるバス停に最初に到達したときが、そのバス停を使う最小乗車回数です。
後から同じバス停に来ても、それ以上よい遷移は生まれないため、1 回だけ処理すれば十分です。

路線数 \(1\) の路線は使えない

問題文では、乗った路線では「現在いるバス停とは異なる」バス停で下車する必要があります。
したがって、通るバス停が 1 つしかない路線は実際には移動に使えません。

コードでもこのような路線は遷移先として使わないようになっています。

アルゴリズム

以下のように BFS を行います。

前処理

• routes[i]: 路線 \(i\) が通るバス停の一覧
• stop_to_routes[x]: バス停 \(x\) を通る路線の一覧

を作ります。

同時に、

• 路線 \(i\) が \(T\) を含むかどうか contains_t[i]
• 路線 \(i\) が \(S\) を含むなら dist[i] = 1 として BFS キューに入れる

を行います。

ただし \(S = T\) のときは、乗車せずに到達できるので答えは \(0\) です。

BFS

dist[i] を「路線 \(i\) に乗るまでに必要な最小乗車回数」とします。

1. キューから路線 r を取り出す
2. r が \(T\) を通るなら、dist[r] が答え
3. 路線 r の各バス停 stop を見る
   • すでに used_stop[stop] = True ならスキップ
   • そうでなければ used_stop[stop] = True
   • stop_to_routes[stop] に含まれるすべての路線 nr について、 まだ未訪問なら dist[nr] = dist[r] + 1 としてキューへ入れる

これで、乗車回数の少ない順に路線を探索できます。

イメージ例

例えば

• 路線 1: \(\{1, 3, 5\}\)
• 路線 2: \(\{5, 7\}\)
• \(S=1, T=7\)

のとき、

• 最初に路線 1 に乗れるので dist[1] = 1
• 路線 1 からバス停 5 に行ける
• バス停 5 を通る路線 2 に乗り換えられるので dist[2] = 2
• 路線 2 は \(T=7\) を含む

よって答えは \(2\) です。

計算量

\(\displaystyle L = \sum_{i=1}^{M} K_i\) とおきます。

• 時間計算量: \(O(N + M + L)\)
• 空間計算量: \(O(N + M + L)\)

理由

• 各路線のバス停一覧を見る回数は合計で \(O(L)\)
• 各バス停は used_stop により高々 1 回だけ展開される
• 各「バス停 ↔ 路線」の対応も高々 1 回ずつしか本質的に使わない

したがって、全体で線形時間に収まります。

実装のポイント

• S == T は先に処理して 0 を出力する

• 路線を BFS の頂点にし、開始路線の距離を 1 にする

• 同じバス停を何度も展開しないために used_stop を使う

• バス停が 1 つしかない路線は移動に使えないので、遷移先として扱わない

• 入力サイズが大きいため、sys.stdin.buffer.read() でまとめて読むと高速です

  ソースコード

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)
    S = next(it)
    T = next(it)

    if S == T:
        print(0)
        return

    routes = [[] for _ in range(M)]
    stop_to_routes = [[] for _ in range(N + 1)]
    contains_t = [False] * M
    dist = [-1] * M
    q = deque()

    for i in range(M):
        k = next(it)
        arr = [0] * k

        if k >= 2:
            has_s = False
            has_t = False
            for j in range(k):
                a = next(it)
                arr[j] = a
                stop_to_routes[a].append(i)
                if a == S:
                    has_s = True
                if a == T:
                    has_t = True
            contains_t[i] = has_t
            if has_s:
                dist[i] = 1
                q.append(i)
        else:
            arr[0] = next(it)

        routes[i] = arr

    used_stop = [False] * (N + 1)
    used_stop[S] = True

    while q:
        r = q.popleft()
        d = dist[r]

        if contains_t[r]:
            print(d)
            return

        for stop in routes[r]:
            if used_stop[stop]:
                continue
            used_stop[stop] = True
            for nr in stop_to_routes[stop]:
                if dist[nr] == -1:
                    dist[nr] = d + 1
                    q.append(nr)

    print(-1)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。