笔试时间：2025年10月22日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

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

输入描述

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

接下来 M 行，每行描述一条地铁线路，首先是一个整数表示该线路上的站点数量，然后是若干个整数，表示该线路上的站点编号（从 0 开始）。

接下来 Q 行，每行包含两个整数 a 和 b，表示一次查询的起点站和终点站。

输出描述

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

样例输入

3 2 2

2 0 1

2 0 2

0 2

0 1

样例输出

0

0

样例说明： 从站点 0 到站点 2，无需换乘直达；从站点 0 到站点 1，无需换乘直达。

参考题解

解题思路：

本题要求计算从起点到终点的最少换乘次数，关键在于将"换乘"作为状态转移的代价。

核心思路：

1. 如果起点和终点在同一条线路上，换乘次数为0
2. 如果需要在不同线路间转换，每次换乘增加1次换乘计数
3. 换乘只能发生在两条线路共有的站点

算法选择：使用BFS（广度优先搜索），因为每次换乘的代价相同（+1）

• 用 dist 数组记录到达每个站点的最少换乘次数
• 用 used_line 标记已经访问过的线路，避免重复处理

具体步骤：

1. 起点相同则直接输出0
2. 从起点出发，标记所有包含起点的线路为已访问
3. 将这些线路上的所有站点加入队列，换乘次数为0
4. BFS过程中，对于当前站点，找到所有经过它的线路，对于每条未访问的线路，换乘次数+1，将该线路上所有未访问的站点加入队列
5. 找到终点站点输出当前换乘次数，队列为空仍未找到则输出-1

C++：

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cstring>
using namespace std;

int main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    
    vector<vector<int>> L(M);
    unordered_map<int, vector<int>> S;
    
    for (int i = 0; i < M; i++) {
        int cnt;
        cin >> cnt;
        for (int j = 0; j < cnt; j++) {
            int station;
            cin >> station;
            L[i].push_back(station);
            S[station].push_back(i);
        }
    }
    
    for (int q = 0; q < Q; q++) {
        int a, b;
        cin >> a >> b;
        
        if (a == b) {
            cout << 0 << endl;
            continue;
        }
        
        vector<int> dist(N, -1);
        vector<bool> used_line(M, false);
        queue<int> que;
        
        for (int lid : S[a]) {
            if (!used_line[lid]) {
                used_line[lid] = true;
                for (int s : L[lid]) {
                    if (dist[s] == -1) {
                        dist[s] = 0;
                        que.push(s);
                    }
                }
            }
        }
        
        bool flag = false;
        while (!que.empty()) {
            int cur = que.front();
            que.pop();
            int t = dist[cur];
            
            if (cur == b) {
                cout << t << endl;
                flag = true;
                break;
            }
            
            for (int nxt_line : S[cur]) {
                if (!used_line[nxt_line]) {
                    used_line[nxt_line] = true;
                    int new_t = t + 1;
                    for (int nxt_st : L[nxt_line]) {
                        if (dist[nxt_st] == -1) {
                            dist[nxt_st] = new_t;
                            que.push(nxt_st);
                        }
                    }
                }
            }
        }
        
        if (!flag) {
            cout << -1 << endl;
        }
    }
    
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int Q = sc.nextInt();
        
        List<List<Integer>> L = new ArrayList<>();
        Map<Integer, List<Integer>> S = new HashMap<>();
        
        for (int i = 0; i < M; i++) {
            int cnt = sc.nextInt();
            List<Integer> line = new ArrayList<>();
            for (int j = 0; j < cnt; j++) {
                int station = sc.nextInt();
                line.add(station);
                S.computeIfAbsent(station, k -> new ArrayList<>()).add(i);
            }
            L.add(line);
        }
        
        for (int q = 0; q < Q; q++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            
            if (a == b) {
                System.out.println(0);
                continue;
            }
            
            int[] dist = new int[N];
            Arrays.fill(dist, -1);
            boolean[] usedLine = new boolean[M];
            Queue<Integer> queue = new LinkedList<>();
            
            if (S.containsKey(a)) {
                for (int lid : S.get(a)) {
                    if (!usedLine[lid]) {
                        usedLine[lid] = true;
                        for (int s : L.get(lid)) {
                            if (dist[s] == -1) {
                                dist[s] = 0;
                                queue.offer(s);
                            }
                        }
                    }
                }
            }
            
            boolean flag = false;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                int t = dist[cur];
                
                if (cur == b) {
                    System.out.println(t);
                    flag = true;
                    break;
                }
                
                if (S.containsKey(cur)) {
                    for (int nxtLine : S.get(cur)) {
                        if (!usedLine[nxtLine]) {
                            usedLine[nxtLine] = true;
                            int newT = t + 1;
                            for (int nxtSt : L.get(nxtLine)) {