CSP-S 提高级 · CSP 2024 提高级第一轮 第 20 题

（次短路） 已知一个有 $n$ 个点 $m$ 条边的有向图 $G$，并且给定图中的两个点 $s$ 和 $t$，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行 $-1$。如果存在，输出两行，第一行表示次短路的长度，第二行表示次短路的一个方案。

#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;

const int maxn = 2e5+10, maxm = 1e6+10, inf = 522133279;

int n, m, s, t;
int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;
int dis[maxn<<1], *dis2;
int pre[maxn<<1], *pre2;
bool vis[maxn<<1];

void add(int a, int b, int c) {
    ++tot;
    nxt[tot] = head[a];
    to[tot] = b;
    w[tot] = c;
    head[a] = tot;
}

bool upd(int a, int b, int d, priority_queue<pair<int, int>> &q) {
    if (d >= dis[b]) return false;
    if (b < n) ___①___;
    q.push(___②___);
    dis[b] = d;
    pre[b] = a;
    return true;
}

void solve() {
    priority_queue<pair<int, int>> q;
    q.push(make_pair(0, s));
    memset(dis, ___③___, sizeof(dis));
    memset(pre, -1, si

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考次短路，核心是把每个点拆成两个状态：最短路和次短路。拿到题先想怎么用 Dijkstra 同时维护这两个距离，队列里存 (距离, 节点)，节点编号小于 n 代表最短路，大于等于 n 代表次短路，更新时注意原来最短路要降级成次短路候选。

最容易栽跟头的是①处：更新到 b 的更短路径时，原 dis[b] 必须作为次短候选推入队列，很多同学只把新距离推一次，忘了把旧的最短路降级；还有②处优先队列默认是大顶堆，必须取负数才能模拟小顶堆，直接填 d 会完全跑反；memset 用 0x3f 是常见的惯性思维，但这里数组很大，0x3f 乘开后溢出，必须用 0x1f 得到 0x1f1f1f1f；输出次短路路径时别搞混 pre 和 pre2 的下标，次短路状态对应的是 pre2[a%n]。

考察知识点

图论算法 — 最短路径 / 次短路

概念定义

• 最短路：从起点到某点的最小权值路径。
• 次短路：长度严格大于最短路的最短路径（即第二小的简单路径长度）。
• 拆点技巧：把每个点拆成两个状态——最短路状态和次短路状态，在 Dijkstra 中同时维护。

命题视角

命题人喜欢考“次短路”这种变体，因为单纯跑 Dijkstra 太模板化，而次短路必须引入“状态分裂”和“降级转移”，考察学生对 Dijkstra 松弛过程的理解深度。挖坑点通常就在： 1. 更新最短路时，原最短路要降级成次短路候选（本题①）； 2. 优先队列的大小比较（本题②）； 3. 无穷大的初始化（本题③）； 4. 次短路更新时的参数（本题④）； 5. 输出路径时对应的前驱数组（本题⑤）。

思考心法与逐空推导

拿到题先看整体设计：

• dis[0..n-1] 存最短路，dis[n..2n-1]（即 dis2）存次短路；
• pre[0..n-1] 存最短路前驱，pre[n..2n-1]（即 pre2）存次短路前驱；
• 队列元素是 pair<距离，节点编号>，编号 < n 代表最短路状态，>= n 代表次短路状态。

① 处：当发现到 b 的更短路径 d 时，如果 d < dis[b]，说明原来的 dis[b] 不再是严格最短路了，它应该降级为次短路的候选。因此要把原来最短路的前驱 pre[b] 指向的新状态 n+b 用原来的距离 dis[b] 推入队列。选项 A upd(pre[b], n+b, dis[b], q) 正确。其他选项要么前驱没取 pre[b]，要么状态没加 n，要么距离没取原来的 dis[b]，都会导致次短路信息丢失。

② 处：C++ 的 priority_queue 默认是大顶堆，我们要的是最小距离先出队，必须把距离取负。选项 A make_pair(-d, b) 正确。填 d 会完全跑反，队列里永远出最大的距离，算法彻底失效。

③ 处：memset 是按字节填充的。0x3f 填充后得到 0x3f3f3f3f，这个值已经超过了题目中边权累加可能达到的最大值（题目给的 inf 是 522133279），而且 0x3f 乘 4 会溢出，导致初始化错误。正确做法是用 0x1f，填充后得到 0x1f1f1f1f，这个值足够大又不会溢出。所以选 B 0x1f。

④ 处：当最短路更新失败（!upd(...)）时，说明当前的 d 不小于 dis[b]，但可能比 dis2[b] 小，这时候要尝试更新次短路。注意此时 aa 是最短路状态（aa < n），所以 a = aa % n 是最短路的前驱，新距离是 dis[a] + c，目标状态是 n+b（次短路）。选项 A upd(a, n+b, dis[a]+c, q) 正确。其他选项要么状态没加 n，要么前驱没取 a，要么距离没取 dis[a]+c，都会导致次短路信息错误。

⑤ 处：输出次短路路径时，从次短路状态 n+t 开始回溯，需要用到次短路的前驱数组 pre2。当前节点是 a = (n+t) % n = t，所以应该取 pre2[t]，即 pre2[a%n]。选项 A 正确。填 pre[a%n] 会回到最短路的前驱，路径就错了。

避坑指南

• 次短路 Dijkstra 最关键的就是“降级转移”：更新最短路时，原最短路必须作为次短路候选推入队列，否则次短路永远无法正确计算。
• 优先队列一定要取负数，这是 C++ 标准库的坑。
• memset 用 0x3f 是惯性思维，但这里数组很大，必须用 0x1f。
• 输出路径时别搞混 pre 和 pre2，次短路状态对应的是 pre2[a%n]。

考频与趋势

图论算法在题库中已考过 26 题，覆盖 3 个级别，其中 CSP 提高级考过 8 题，本题正是 2024 年 CSP 提高级的题目，属于该级别的高频考点。最短路径相关题目共 35 题，CSP 提高级考过 5 题，2024 年考了 6 题，2025 年考了 7 题，2026 年考了 7 题，说明最短路径及其变体（如次短路、第 K 短路）在提高级中非常活跃，未来几年仍会持续出现。

预测

基于 2024-2026 年最短路径类题目在 CSP 提高级中连续三年高频出现（2024 年 6 题、2025 年 7 题、2026 年 7 题），且本题作为 2024 年提高级第 20 题（压轴位置）出现，可以预测未来 CSP 提高级仍会频繁考察最短路径的变体，如次短路、第 K 短路、最短路方案数等。命题人可能会继续利用“拆点”“降级转移”等技巧挖坑，尤其是优先队列的大小比较和 memset 的字节填充这类细节，仍将是高频考点。暂无足够依据预测具体的年份和题号，但方向明确：最短路径及其变体将继续是 CSP 提高级的重头戏。