星际跃迁网络

题意

有 $n$ 个星系（编号从 0 开始）和 $m$ 条跃迁航线，每条航线经过若干个星系。如果两条航线经过同一个星系，探险家可以在该星系进行「航线换乘」。给 $q$ 个查询，每次问从星系 $s$ 到星系 $t$ 最少需要多少次换乘，不可达输出 $-1$ 。

思路

先想清楚「换乘」是什么意思：你从起点出发，先坐上某条航线，这条航线能直达的所有星系你都能到，不需要换乘。如果目的地不在这条航线上，你就得在某个共享星系跳到另一条航线，这算一次换乘。

所以本质上，如果起点和终点在同一条航线上，答案是 0；如果需要经过两条航线，答案是 1；以此类推。

那怎么高效算这个最少换乘次数？

关键建模：二部图 BFS

把星系和航线都看成节点，构建一个二部图：

星系节点： $0, 1, \ldots, n-1$
航线节点： $n, n+1, \ldots, n+m-1$
如果星系 $g$ 在航线 $i$ 上，就连一条边 $g \leftrightarrow (n+i)$

在这个二部图上从 $s$ 做 BFS，到达 $t$ 的最短距离 $d$ 一定是偶数（因为路径总是星系→航线→星系→航线→……→星系），而换乘次数就是：

$ $\text{换乘次数} = \frac{d}{2} - 1$ $

为什么减 1？因为第一次「坐上航线」不算换乘，只有从一条航线切换到另一条才算。 $d/2$ 代表经过了多少条航线，减掉第一条就是换乘次数。

拿样例验证一下：查询 $2 \to 5$ ，BFS 路径是星系2 → 航线6 → 星系3 → 航线7 → 星系5，距离 $d=4$ ，换乘次数 $= 4/2 - 1 = 1$ ，和预期一致。

为什么不直接建航线之间的图？

你可能想到另一种做法：如果两条航线共享至少一个星系，就连一条边，然后在航线图上 BFS。这当然可以，但建图的代价可能很高——两两航线判共享星系，最坏情况下是 $O(\sum k_i^2)$ 。而二部图的边数就是 $\sum k_i$ （每条航线的星系数之和），建图更直接，BFS 也更轻量。

复杂度

时间：每次查询 $O(n + m + \sum k_i)$ ，总共 $O(q \cdot (n + m + \sum k_i))$
空间： $O(n + m + \sum k_i)$

代码

C++
Java
Python3
JavaScript

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<int>> adj(n + m);

    for(int i = 0; i < m; i++){
        int k;
        cin >> k;
        int routeNode = n + i;
        for(int j = 0; j < k; j++){
            int g;
            cin >> g;
            adj[g].push_back(routeNode);
            adj[routeNode].push_back(g);
        }
    }

    while(q--){
        int s, t;
        cin >> s >> t;

        if(s == t){
            cout << 0 << "\n";
            continue;
        }

        vector<int> dist(n + m, -1);
        queue<int> bfs;
        dist[s] = 0;
        bfs.push(s);
        bool found = false;

        while(!bfs.empty()){
            int u = bfs.front(); bfs.pop();
            if(u == t){
                cout << dist[t] / 2 - 1 << "\n";
                found = true;
                break;
            }
            for(int v : adj[u]){
                if(dist[v] == -1){
                    dist[v] = dist[u] + 1;
                    bfs.push(v);
                }
            }
        }

        if(!found) cout << -1 << "\n";
    }

    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        int total = n + m;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < total; i++) adj.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int routeNode = n + i;
            for (int j = 0; j < k; j++) {
                int g = Integer.parseInt(st.nextToken());
                adj.get(g).add(routeNode);
                adj.get(routeNode).add(g);
            }
        }

        int[] dist = new int[total];
        for (int qi = 0; qi < q; qi++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            if (s == t) {
                sb.append(0).append('\n');
                continue;
            }

            Arrays.fill(dist, -1);
            Queue<Integer> bfs = new LinkedList<>();
            dist[s] = 0;
            bfs.add(s);
            boolean found = false;

            while (!bfs.isEmpty()) {
                int u = bfs.poll();
                if (u == t) {
                    sb.append(dist[t] / 2 - 1).append('\n');
                    found = true;
                    break;
                }
                for (int v : adj.get(u)) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        bfs.add(v);
                    }
                }
            }

            if (!found) sb.append(-1).append('\n');
        }

        System.out.print(sb);
    }
}

import sys
from collections import deque

input = sys.stdin.readline

def main():
    n, m, q = map(int, input().split())
    total = n + m
    adj = [[] for _ in range(total)]

    for i in range(m):
        parts = list(map(int, input().split()))
        k = parts[0]
        routeNode = n + i
        for j in range(1, k + 1):
            g = parts[j]
            adj[g].append(routeNode)
            adj[routeNode].append(g)

    out = []
    for _ in range(q):
        s, t = map(int, input().split())
        if s == t:
            out.append('0')
            continue

        dist = [-1] * total
        dist[s] = 0
        bfs = deque([s])
        found = False

        while bfs:
            u = bfs.popleft()
            if u == t:
                out.append(str(dist[t] // 2 - 1))
                found = True
                break
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    bfs.append(v)

        if not found:
            out.append('-1')

    sys.stdout.write('\n'.join(out) + '\n')

main()

const readline = require('readline');

const rl = readline.createInterface({ input: process.stdin });
const lines = [];

rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const [n, m, q] = lines[idx++].split(' ').map(Number);
    const total = n + m;
    const adj = new Array(total);
    for (let i = 0; i < total; i++) adj[i] = [];

    for (let i = 0; i < m; i++) {
        const parts = lines[idx++].split(' ').map(Number);
        const k = parts[0];
        const routeNode = n + i;
        for (let j = 1; j <= k; j++) {
            const g = parts[j];
            adj[g].push(routeNode);
            adj[routeNode].push(g);
        }
    }

    const out = [];
    const dist = new Int32Array(total);

    for (let qi = 0; qi < q; qi++) {
        const [s, t] = lines[idx++].split(' ').map(Number);
        if (s === t) {
            out.push('0');
            continue;
        }

        dist.fill(-1);
        dist[s] = 0;
        const bfs = [s];
        let head = 0;
        let found = false;

        while (head < bfs.length) {
            const u = bfs[head++];
            if (u === t) {
                out.push(String(dist[t] / 2 - 1));
                found = true;
                break;
            }
            const neighbors = adj[u];
            for (let i = 0; i < neighbors.length; i++) {
                const v = neighbors[i];
                if (dist[v] === -1) {
                    dist[v] = dist[u] + 1;
                    bfs.push(v);
                }
            }
        }

        if (!found) out.push('-1');
    }

    console.log(out.join('\n'));
});