Overview

In a city with \(N\) bus stops and \(M\) bus routes, the problem asks for the minimum number of rides to travel from bus stop \(S\) to bus stop \(T\). Each route contains multiple bus stops, and you can travel between any two bus stops within the same route in a single ride.

Analysis

Problem with a Naive Graph Construction

If we think of this problem as a graph where “bus stops are vertices and edges connect bus stops on the same route,” then a route with \(K\) bus stops would require \(K(K-1)/2\) edges just within that route. The constraint is \(\sum K_i \leq 5 \times 10^5\), but for example, if a single route contains all bus stops, the number of edges reaches \(O(N^2)\), exceeding the time limit (TLE) or memory limit (MLE).

The Trick: Treating Routes as “Vertices”

The key insight is to treat not only “bus stops” but also “bus routes” as vertices in the graph. Specifically, we construct a graph with the following \(N + M\) vertices: - Vertices representing bus stops: \(1, 2, \dots, N\) - Vertices representing bus routes: \(N+1, N+2, \dots, N+M\)

Then, if bus route \(i\) passes through bus stop \(u\), we add an edge between “bus stop \(u\)” and “bus route \(N+i\)”. With this technique, the total number of edges becomes \(\sum K_i\), which is a manageable size within the constraints.

Algorithm

On this constructed graph, we find the shortest path using Breadth-First Search (BFS).

1. Bipartite Graph Construction: When bus stop \(u\) is included in route \(i\), add an undirected edge \((u, N+i)\).

2. Running BFS: Starting from bus stop \(S\), compute the shortest distance dist to each vertex.

   • Initial state: dist[S] = 0, all other vertices are -1 (unvisited).
   • Add \(S\) to the queue and begin the search.

3. Computing the Answer: Movement in this graph always alternates as “bus stop \(\to\) route \(\to\) bus stop \(\to\) route \(\dots\)”.

   • Moving from bus stop \(S\) to some route \(i\) (increasing dist by 1) corresponds to “boarding that route.”
   • Moving from that route \(i\) to another bus stop \(v\) (increasing dist by 1 again) corresponds to “alighting from that route.”

   Therefore, if the shortest distance from bus stop \(S\) to bus stop \(T\) is \(D\), the actual number of rides is \(D / 2\).

Complexity

• Time Complexity: \(O(N + M + \sum K_i)\)
  • The graph has \(N+M\) vertices and \(\sum K_i\) edges. BFS visits each vertex and each edge a constant number of times, so it runs in linear time.
• Space Complexity: \(O(N + M + \sum K_i)\)
  • This is the memory required to store the adjacency list and the distance array.

Implementation Tips

• Fast I/O: In Python, since the number of input lines can be large, reading all input at once using sys.stdin.read().split() is faster.

• Early Termination at Destination: During BFS, if we reach destination \(T\), we can immediately output dist[T] // 2 and terminate, providing a slight speedup. If \(T\) is never reached after the entire search, output -1.

  Source Code

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()

This editorial was generated by gemini-3-flash-thinking.