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

题目

（次短路） 已知一个有 $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. pre2[a%n]
• B. pre[a%n]
• C. pre2[a]
• D. pre[a%n]+1

答案

A

题解

选 A. pre2[a%n]。

程序把每个点拆成两种状态：

• 0 ~ n-1：到达该点的最短路。
• n ~ 2n-1：到达该点的次短路。

pre 数组记录每个状态的前驱，且代码中有：

``cpp pre2 = pre + n; ``

因此，当 a >= n 时：

``cpp pre2[a%n] == pre[n + a%n] == pre[a] ``

它就是当前次短路状态的前驱，可以继续递归还原路径，所以应填：

``cpp else out(pre2[a%n]); ``

注意，前驱可能是最短路状态，也可能是次短路状态；pre2[a%n] 已经保存了完整的状态编号，无须再加 n。