今問題は超頂点を用意したグラフ上で 01BFS を行うことで解けます。

各バス停を頂点としてBFSなどを行おうとすると、辺が \(\Theta(N^2)\) 個存在するケースが存在するため解けません。そこで、各バス停に加え「路線 \(i\) のバスに乗車中である」という状態を表す \(M\) 個の頂点を追加した \(N+M\) 頂点のグラフを考えます。

バスに降りるときにコストを払うと考え、

• 路線 \(i\) が通るバス停から「路線 \(i\) に乗車中」へコスト \(0\) の辺
• 「路線 \(i\) に乗車中」から路線 \(i\) が通るバス停へコスト \(1\) の辺

を張ったグラフにおける最小コストが求めるコストに一致します。このグラフの辺の個数は \(2\sum K_i\) 個であるため、全体で \(O(N+M+2\sum K_i)\) 時間でこの問題を解くことができました。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m, s, t;
  cin >> n >> m >> s >> t;
  s--, t--;
  vector<vector<pair<int,int>>>G(n+m);
  // 0からN-1がバス停、N+0からN+M-iが路線を表す

  for(int i=0; i<m; i++){
    int k;
    cin >> k;
    for(int j=0; j<k; j++){
      int a;
      cin >> a;
      a--;
      G[a].push_back({n+i, 0});
      G[n+i].push_back({a, 1});
    }
  }

  deque<int>q;
  long long INF = 1000000000000000000;
  vector<long long>dist(n+m, INF);
  dist[s] = 0;
  q.push_back(s);
  while(q.size() > 0){
    int v = q.front(); q.pop_front();
    for(auto[vv, c]: G[v]){
      if(dist[vv] > dist[v] + c){
        dist[vv] = dist[v] + c;
        if(c == 0){
          q.push_front(vv);
        }else{
          q.push_back(vv);
        }
      }
    }
  }

  if(dist[t] == INF){
    cout << -1 << endl;
  }else{
    cout << dist[t] << endl;
  }
}

実装例 (Python)

from collections import deque

N, M, S, T = map(int, input().split())
S -= 1
T -= 1
G=[[] for _ in range(N+M)]
# 0からN-1がバス停、N+0からN+M-iが路線を表す

for i in range(M):
  K, *A = map(int, input().split())
  for a in A:
    a -= 1
    G[a].append((N+i, 0))
    G[N+i].append((a, 1))

INF = 10**18
dist = [INF]*(N+M)
dist[S] = 0
q = deque()
q.append(S)
while len(q) > 0:
  v = q.popleft()
  for vv, c in G[v]:
    if dist[vv] > dist[v] + c:
      dist[vv] = dist[v] + c
      if c == 0:
        q.appendleft(vv)
      else:
        q.append(vv)

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