概要

「1回の乗車で、同じ路線内のどのバス停へも移動できる」という性質を使い、バス停を頂点とした BFS で最小乗車回数を求める問題です。
ただし同じ路線を何度も展開すると遅くなるため、各路線は一度だけ使うのがポイントです。

考察

重要な観察は次の2つです。

1. あるバス停 \(u\) に乗車回数 \(d\) で到達しているとき、
   \(u\) を通る任意の路線 \(r\) に1回乗れば、その路線上のすべてのバス停へ \(d+1\) 回で行ける。
2. 路線 \(r\) を一度展開（その路線上の全バス停への緩和）した後、
   別のバス停から再び同じ路線 \(r\) を展開しても、新しい情報は基本的に増えず無駄になりやすい。

素朴に「各バス停から、そのバス停を通る全路線、さらにその路線上の全バス停」を毎回たどると、同じ路線を何度も走査してしまい、最悪で非常に重くなります。
そこで used_route[r] を持ち、各路線を最初に使った1回だけ処理します。

これにより、各バス停は必要なときにキューへ入り、各路線は1回だけ全停留所をなめるので、全体を制約内で高速に処理できます。

アルゴリズム

1. 入力から以下を作る。
   • routes[r]: 路線 \(r\) が通るバス停のリスト
   • stop_to_routes[s]: バス停 \(s\) を通る路線番号のリスト（逆引き）
2. dist_stop[s] を「バス停 \(s\) への最小乗車回数」として、初期値を \(\infty\)、dist_stop[S]=0。
3. キューで BFS を行う。
   • バス停 u を取り出す。u==T ならその距離を出力して終了。
   • u を通る各路線 r について、未使用なら使用済みにする。
   • 路線 r 上の各バス停 v に対し、dist_stop[v] > dist_stop[u] + 1 なら更新してキューへ入れる。
4. BFS が終わっても T に到達しなければ -1。

この BFS は「1回の乗車」をちょうど1コストとして層状に広がるため、最初に T に到達した回数が最小です。

計算量

• 時間計算量: \(O\!\left(N + \sum K_i\right)\)（厳密には入力読込分を含めて同程度）
• 空間計算量: \(O\!\left(N + M + \sum K_i\right)\)

（理由）
各路線は used_route により高々1回だけ展開され、各展開でその路線の停留所数ぶんだけ処理するため、路線側の総処理は \(\sum K_i\) 回です。

実装のポイント

• stop_to_routes（停留所→路線）を作っておくと、現在地から乗れる路線を即座に列挙できます。

• used_route が最重要。これがないと同じ路線を何度もなめて遅くなります。

• S==T の場合も、BFS開始直後に u==T で 0 を正しく返せます。

• 距離配列は十分大きい値 (INF) で初期化し、if dist_stop[v] > nd: で更新判定するのが安全です。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M, S, T = map(int, input().split())

    routes = []
    stop_to_routes = [[] for _ in range(N + 1)]

    for i in range(M):
        data = list(map(int, input().split()))
        k = data[0]
        stops = data[1:]
        routes.append(stops)
        for s in stops:
            stop_to_routes[s].append(i)

    INF = 10**18
    dist_stop = [INF] * (N + 1)
    used_route = [False] * M

    q = deque()
    dist_stop[S] = 0
    q.append(S)

    while q:
        u = q.popleft()
        d = dist_stop[u]
        if u == T:
            print(d)
            return

        for r in stop_to_routes[u]:
            if used_route[r]:
                continue
            used_route[r] = True
            nd = d + 1
            for v in routes[r]:
                if dist_stop[v] > nd:
                    dist_stop[v] = nd
                    q.append(v)

    print(-1)

if __name__ == "__main__":
    main()

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