1 条题解

  • 0
    @ 2026-11-11 23:35:55

    题意简述

    每条线路是可双向上下车的一组站点;求从站点 11 到站点 nn 的最少换乘次数(上车的第一条线路不计),不可达输出 −1-1。

    思路

    关键转化:

    "换乘"发生在两条线路之间,直接以"换乘次数"为距离不好转移。注意:

    换乘次数 = 乘坐的线路数 − 1-\,1

    于是问题变成:从站点 1 到站点 n 最少要乘坐多少条线路。若到达 nn 至少要坐 KK 条线路,答案就是 K−1K - 1。

    BFS:

    把距离定义在站点上:dist[s] = 从 11 到 ss 最少乘坐的线路数,dist[1] = 0。

    转移:已用 dd 条线路到达站点 uu,那么 uu 所在的每条还没坐过的线路 LL,都能把 LL 上的全部站点以 d+1d + 1 条线路到达(坐 LL 本身不算换乘,但 LL 计为新乘坐的一条线路)。而坐已经坐过的线路不会更优——它当初被触达时,它的所有站点已经以某个不超过当前值的距离入过队了。

    于是做 BFS,队列里放站点:

    1. 弹出站点 uu;
    2. 对 uu 所在的每条未标记线路 LL:打标记,把 LL 上所有 dist 为 −1-1 的站点置为 dist[u] + 1 并入队;
    3. 队列空后,答案为:若 dist[n] = -1 则 −1-1,否则 dist[n] - 1。

    为什么每条线路只需展开一次:BFS 按 dist 非降出队,一条线路第一次被触发时,触发它的站点是这条线路上 dist 最小的;之后再触发不可能更小。

    等价模型(用于对拍验证):在"线路图"(点 = 线路,两条线路共站即连边)上从"含站点 1 的线路"出发 BFS,层数即线路数,答案同样减 1。两个模型结论一致,互为正确性校验。

    一个常见但不对的思路:

    把同线任意两站当作单位边建"站点图"后跑普通 BFS,得到的是经过站点数最少,与换乘最少是两个不同目标(例:一条直达线跨 50 站、换乘 0 次;两条各乘 1 站换乘 1 次——按"站点数"前者更差,按"换乘数"前者更优)。若强行在状态里加入"当前所在线路",状态变成 (站点, 线路),规模乘 mm,虽然也能过,但不如上面的刻度简洁。

    复杂度

    每条线路至多展开一次,摊还 O(ki)O(k_i);总时间 O(n+m+∑ki)O(n + m + \sum k_i),空间同阶。m≤500m \le 500、∑ki≤5×104\sum k_i \le 5 \times 10^4,轻松通过。

    参考代码(C++)

    #include <cstdio>
    #include <vector>
    #include <deque>
    using namespace std;
    
    int main() {
        freopen("bus.in", "r", stdin);
        freopen("bus.out", "w", stdout);
    
        int n, m;
        scanf("%d %d", &n, &m);
        vector<vector<int>> lineStops(m);
        vector<vector<int>> linesAt(n + 1);
        for (int i = 0; i < m; i++) {
            int k;
            scanf("%d", &k);
            lineStops[i].resize(k);
            for (int j = 0; j < k; j++) {
                scanf("%d", &lineStops[i][j]);
                linesAt[lineStops[i][j]].push_back(i);
            }
        }
        vector<int> dist(n + 1, -1);      // dist[s]: 到达 s 最少乘坐的线路数
        vector<bool> expanded(m, false);  // 该线路是否已被展开
        deque<int> q;
        dist[1] = 0;
        q.push_back(1);
        while (!q.empty()) {
            int u = q.front();
            q.pop_front();
            for (int L : linesAt[u]) {
                if (expanded[L]) continue;
                expanded[L] = true;
                for (int v : lineStops[L])
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        q.push_back(v);
                    }
            }
        }
        printf("%d\n", dist[n] == -1 ? -1 : dist[n] - 1);
        return 0;
    }
    

    易错点

    1. 忘减 1:样例 1 中 dist[n] = 3,输出 22;站点 1、nn 同线时 dist[n] = 1,输出 00。
    2. 不可达输出 −1-1:注意 dist[n] = -1 既是哨兵又是答案,输出前判断即可,不要把哨兵当距离再减 1 变成 −2-2。
    3. 线路双向运行:不要按输入顺序当作有向线路。
    4. BFS 深度由线路数决定而不是站点数(测试点 10 是 500 条线路串成的链、换乘 499 次),手写循环队列时别按 nn 估计大小;用递归 DFS 也会爆栈。
    5. 同一线路内站点互不相同是题目保证,不必去重;但"不重复乘坐一条线路"要靠线路标记实现,不能只靠站点标记。

    测试点设计

    测试点 设计意图
    1–3 题面样例(答案 22 / −1-1 / 00)
    4 最小规模 n=2n=2,单条线路同时含 11、nn
    5 4 条线路链,答案 33
    6 手工构造,答案 22
    7 5 条线路全含站点 1 但都不含 nn:−1-1
    8–9 随机(小 / 中)
    10 n=501n=501,500500 条 {i,i+1}\{i, i+1\} 长链:答案 499499,卡队列开小 / 递归爆栈
    11 n=1000n=1000、m=500m=500 满规模随机(已排除"某线同时含 11 与 nn"的平凡情形)
    12 满规模随机连通图
    • 1

    信息

    ID
    5
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    2
    已通过
    2
    上传者