CSP-S 2024 第一轮 第41题：完善程序（第 20 题）第 4 空

题目

（次短路） 已知一个有 $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, sizeof(pre));
    dis2 = dis+n;
    pre2 = pre+n;
    dis[s] = 0;
    while (!q.empty()) {
        int aa = q.top().second; q.pop();
        if (vis[aa]) continue;
        vis[aa] = true;
        int a = aa % n;
        for (int e = head[a]; e; e = nxt[e]) {
            int b = to[e], c = w[e];
            if (aa < n) {
                if (!upd(a, b, dis[a]+c, q))
                    _④;
            } else
                upd(n+a, n+b, dis2[a]+c, q);
        }
    }
}

void out(int a) {
    if (a != s) {
        if (a < n) out(pre[a]);
        else out(_⑤_);
    }
    printf("%d%c", a%n+1, " \n"[a == n+t]);
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    s--, t--;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a-1, b-1, c);
    }
    solve();
    if (dis2[t] == inf) puts("-1");
    else {
        printf("%d\n", dis2[t]);
        out(n+t);
    }
}

④ 处应填（  ）

选项

• A. upd(a, n+b, dis[a]+c, q)
• B. upd(n+a, n+b, dis2[a]+c, q)
• C. upd(n+a, b, dis2[a]+c, q)
• D. upd(a, b, dis[a]+c, q)

答案

A

题解

选 A：upd(a, n+b, dis[a]+c, q)。

这段程序把每个点分成两种状态：

• b：到点 b 的最短路，长度存于 dis[b]。
• n+b：到点 b 的次短路，长度存于 dis2[b]。

执行到④时，aa < n，说明当前从点 a 的最短路出发，经过边 a → b，得到候选长度： ``cpp dis[a] + c ``

前面的 upd(a, b, dis[a]+c, q) 更新最短路失败，因此这里要尝试用这个候选更新 b 的次短路： ``cpp upd(a, n+b, dis[a]+c, q); ``

三个参数分别表示：前驱状态是 a，目标状态是 n+b，候选长度是 dis[a]+c。因此选 A。

但题面代码有一个严格性问题：更新最短路失败只说明候选长度 大于或等于 最短路；相等时不能作为题目要求的次短路。严谨写法应是： ``cpp if (dis[a] + c > dis[b]) upd(a, n+b, dis[a]+c, q); `` 所以 A 是四个选项中的预期答案，但直接填入后，代码仍缺少排除等长路径的判断。