解题思路

• 把“地铁线路上的连续乘坐”看作在同一条线路内行走不增加换乘次数，只有从一条线路换到另一条线路才计一次换乘。

• 建模为线路图：每条地铁线路是一条图上的点；若两条线路在某个站有交集，则两点之间连一条边。

• 查询从起点站 s 到终点站 t 的最少换乘次数：

  • 找出包含 s 的所有线路作为起点集合，包含 t 的所有线路作为目标集合。
  • 若两集合有交集，答案为 0；否则在线路图上对起点集合做BFS，第一次到达目标集合中的任意线路时的层数即最少换乘次数。

• 关键算法：建图 + BFS 最短路（无权图）。

• 实现要点：

  1. 先用“站点 → 经过它的所有线路”的倒排表构建；
  2. 对每个站点，把经过它的所有线路两两连边，得到线路图；
  3. 每个查询在线路图上做一次 BFS（起点多源）。

复杂度分析

• 设线路数为 m，站点数为 n，第 i 个站点被 c_i 条线路经过。
• 建图：对每个站点把 c_i 条线路两两连边，复杂度 O(∑ c_i^2)；通常不超过 O(m^2)。
• 单次查询 BFS：O(m + E)，其中 E 为线路图边数；空间 O(m + E)。
• 在题目给定范围内（n, m, k ≤ 1000），该复杂度完全可接受。

代码实现

Python

# -*- coding: utf-8 -*-
import sys
from collections import deque

def build_graph(n, m, lines):
    """构建：站点->线路、线路图邻接表"""
    station_lines = [[] for _ in range(n)]
    for li, stations in enumerate(lines):
        for s in stations:
            station_lines[s].append(li)

    adj = [set() for _ in range(m)]
    # 同一站点上的所有线路两两连边
    for s in range(n):
        lst = station_lines[s]
        L = len(lst)
        for i in range(L):
            a = lst[i]
            for j in range(i + 1, L):
                b = lst[j]
                adj[a].add(b)
                adj[b].add(a)
    # 转为列表，便于遍历
    adj = [list(nei) for nei in adj]
    return station_lines, adj

def min_transfers_for_query(s, t, station_lines, adj):
    """在线路图上求最少换乘次数"""
    if s == t:
        return 0
    starts = station_lines[s]
    targets = set(station_lines[t])
    if not starts or not targets:
        return -1
    # 若有一条线路同时包含 s 与 t，换乘为 0
    for x in starts:
        if x in targets:
            return 0

    m = len(adj)
    dist = [-1] * m
    q = deque()
    for x in starts:
        dist[x] = 0
        q.append(x)

    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1  # 换乘一次
                if v in targets:
                    return dist[v]
                q.append(v)
    return -1  # 不可达

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    n, m, k = next(it), next(it), next(it)  # 站点数、线路数、查询数

    lines = []
    for _ in range(m):
        cnt = next(it)              # 本线路站点数量
        stations = [next(it) for _ in range(cnt)]
        lines.append(stations)

    station_lines, adj = build_graph(n, m, lines)

    out = []
    for _ in range(k):
        s, t = next(it), next(it)
        out.append(str(min_transfers_for_query(s, t, station_lines, adj)))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

Java

// ACM 风格，类名 Main
// 思路：构建站点->线路倒排表，再把同站点上的线路两两连边；每次查询在“线路图”上做 BFS。
import java.io.*;
import java.util.*;

public class Main {

    // 计算一次查询的最少换乘
    static int bfsMinTransfers(int s, int t, List<Integer>[] stationLines, List<Integer>[] adj) {
        if (s == t) return 0;
        List<Integer> starts = stationLines[s];
        List<Integer> tlist = stationLines[t];
        if (starts.isEmpty() || tlist.isEmpty()) return -1;

        // 目标集合转为布尔标记，O(1) 判断
        int m = adj.length;
        boolean[] isTarget = new boolean[m];
        for (int x : tlist) isTarget[x] = true;

        // 同一条线路同时包含 s 与 t
        for (int x : starts) if (isTarget[x]) return 0;

        int[] dist = new int[m];
        Arrays.fill(dist, -1);
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int x : starts) { dist[x] = 0; q.add(x); }

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    if (isTarget[v]) return dist[v];
                    q.add(v);
                }
            }
        }
        return -1;
    }

    // 构建站点->线路、线路图
    static void buildGraph(int n, int m, List<Integer>[] lines,
                           List<Integer>[] stationLines, List<Integer>[] adj) {
        // 建立站点->线路
        for (int i = 0; i < m; i++) {
            for (int s : lines[i]) {
                stationLines[s].add(i);
            }
        }
        // 同站点上的线路两两连边
        for (int s = 0; s < n; s++) {
            List<Integer> lst = stationLines[s];
            int L = lst.size();
            for (int i = 0; i < L; i++) {
                int a = lst.get(i);
                for (int j = i + 1; j < L; j++) {
                    int b = lst.get(j);
                    adj[a].add(b);
                    adj[b].add(a);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        // 默认用 BufferedReader + StringTokenizer，数据范围小也足够
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        @SuppressWarnings("unchecked")
        List<Integer>[] lines = new ArrayList[m];
        for (int i = 0; i < m; i++) lines[i] = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken());
            for (int j = 0; j < cnt; j++) {
                lines[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        @SuppressWarnings("unchecked")
        List<Integer>[] stationLines = new ArrayList[n];
        @SuppressWarnings("unchecked")
        List<Integer>[] adj = new ArrayList[m];
        for (int i = 0; i < n; i++) stationLines[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) adj[i] = new ArrayList<>();

        buildGraph(n, m, lines, stationLines, adj);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            sb.append(bfsMinTransfers(s, t, stationLines, adj)).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// 思路同上：线路做点、同站相交的线路连边，查询时在线路图上 BFS。
#include <bits/stdc++.h>
using namespace std;

// 求一次查询的最少换乘
int bfs_min_transfers(int s, int t,
                      const vector<vector<int>>& stationLines,
                      const vector<vector<int>>& adj) {
    if (s == t) return 0;
    const vector<int>& starts = stationLines[s];
    const vector<int>& tlist  = stationLines[t];
    if (starts.empty() || tlist.empty()) return -1;

    int m = (int)adj.size();
    vector<char> isTarget(m, 0);
    for (int x : tlist) isTarget[x] = 1;
    for (int x : starts) if (isTarget[x]) return 0;

    vector<int> dist(m, -1);
    queue<int> q;
    for (int x : starts) { dist[x] = 0; q.push(x); }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                if (isTarget[v]) return dist[v];
                q.push(v);
            }
        }
    }
    return -1; // 不可达
}

// 构建站点->线路与线路图
void build_graph(int n, int m, const vector<vector<int>>& lines,
                 vector<vector<int>>& stationLines,
                 vector<vector<int>>& adj) {
    for (int i = 0; i < m; ++i) {
        for (int s : lines[i]) {
            stationLines[s].push_back(i);
        }
    }
    for (int s = 0; s < n; ++s) {
        const auto& lst = stationLines[s];
        for (int i = 0; i < (int)lst.size(); ++i) {
            int a = lst[i];
            for (int j = i + 1; j < (int)lst.size(); ++j) {
                int b = lst[j];
                adj[a].push_back(b);
                adj[b].push_back(a);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;

    vector<vector<int>> lines(m);
    for (int i = 0; i < m; ++i) {
        int cnt; cin >> cnt;
        lines[i].resize(cnt);
        for (int j = 0; j < cnt; ++j) cin >> lines[i][j];
    }

    vector<vector<int>> stationLines(n);
    vector<vector<int>> adj(m);
    build_graph(n, m, lines, stationLines, adj);

    for (int i = 0; i < k; ++i) {
        int s, t; cin >> s >> t;
        cout << bfs_min_transfers(s, t, stationLines, adj) << "\n";
    }
    return 0;
}

题目内容

在一个城市的地铁交通网络，有 $M$ 条地铁线路和 $N$ 个地铁站点，每个地铁站都是一个节点，从 $0$开始按照顺序编号，如果两条不同的地铁线路在同一个地铁站点交汇，表示可以在这个地铁站点从一条地铁线路换乘到另一条线路，即两条线路上出现相同的站点编号意味着是个换乘点，这个地铁站点对于两条地铁线路来说是连通的。现在根据给定需要查询的地铁行程路线（从起始地铁站点到终点地铁站点），请给出这些地铁行程路线的最少地铁线路换乘次数。

输入描述

第一行包含三个整数 $n、m$ 和 $k$ ，分别表示站点数量、地铁线路数量和需要查询的起点站和终点站的组合数量。

接下来 $m$ 行，每行描述一条地铁线路，首先是一个整数 $n$ 表示该线路上的站点数量，然后是 $n$ 个整数，表示线路上的站点编号(从 $0$ 开始)。

接下来 $k$ 行，每行包含两个整数 $s$ 和 $t$ ，表示一次查询的起点站和终点站。$n,m,k$ 取值范围在 $[0,1000)$

输出描述

对于每次查询，输出一个整数，要示从起点站到终点站的最少换乘次数，如果无法到达，则输出 $-1$ .

样例1

输入

3 2 2
2 0 1
2 0 2
0 2
0 1

输出

0
0

说明

从站点 $0$ 到站点 $2$ ，无需换乘直达

从站点 $0$ 到站点 $1$ ，无需换乘直达

样例2

输入

4 2 2
3 0 1 2
3 1 2 3
0 3
1 3

输出

1
0

说明

从站点 $0$ 到站点 $3$ ，最少需要换乘 $1$ 次(例如，从 $0$ 到 $1$ (线路 $1$ )，然后换乘到线路 $2$ 的 $2$ 站，再到 $3$ 站)；从站点 $1$ 到站点 $3$ ，不需要换乘(都在线路 $2$ 上)。