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

题目

（次短路） 已知一个有 $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(pre[b], n+b, dis[b], q)
• B. upd(a, n+b, d, q)
• C. upd(pre[b], b, dis[b], q)
• D. upd(a, b, d, q)

答案

A

题解

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

这段程序用两组状态维护距离：

• dis[b]：到点 b 的最短距离，前驱为 pre[b]。
• dis[n+b]：到点 b 的严格次短距离，前驱为 pre[n+b]。

看 upd 的开头：

``cpp if (d >= dis[b]) return false; ``

执行到①时，说明 d < dis[b]。如果 b < n，就是发现了到 b 的更短路径。此时，原来的最短路应成为次短路的候选，因此在覆盖它之前，要执行：

``cpp upd(pre[b], n+b, dis[b], q); ``

这里三个参数分别表示：原最短路的前驱、次短路状态、原最短距离。随后再用 d 和 a 更新最短路。

例如，原最短距离为 10，新找到距离为 7 的路径，就先拿 10 更新次短距离，再把最短距离改为 7。

其他选项：

• B：把新最短距离 d 也存入次短路，不符合“严格大于”。
• C：传入的距离就是 dis[b]，会被第一行直接拒绝。
• D：用相同参数再次调用自身，会无限递归。