CSP-S 2025 第一轮 第37题：完善程序第 1 题 · 第 4 空

题目

（特殊最短路）给定一个含 $N$ 个点、$M$ 条边的带权无向图，边权非负。起点为 $S$，终点为 $T$。对于一条 $S$ 到 $T$ 的路径，可以在整条路径中，至多选择一条边作为“免费边”：当第一次经过这条被选中的边时，费用视为 0；如果之后再次经过该边，则仍按其原始权重计费。点和边均允许重复经过。求从 $S$ 到 $T$ 的最小总费用。

以下代码求解了上述问题。试补全程序。

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const long long INF = 1e18;

struct Edge {
    int to;
    int weight;
};

struct State {
    long long dist;
    int u;
    int used_freebie; // 0 for not used, 1 for used
    bool operator>(const State &other) const {
        return dist > other.dist;
    }
};

int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;

    vector<vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<vector<long long>> d(n + 1, vector<long long>(2, INF));
    priority_queue<State, vector<State>, greater<State>> pq;

    d[s][0] = 0;
    pq.push({0, s, ①});

    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();

        long long dist = current.dist;
        int u = current.u;
        int used = current.used_freebie;

        if (dist > ②) {
            continue;
        }

        for (const auto &edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;

            if (d[u][used] + w < ③) {
                ③ = d[u][used] + w;
                pq.push({③, v, used});
            }

            if (used == 0) {
                if (④ < d[v][1]) {
                    d[v][1] = d[u][used];
                    pq.push({d[v][1], v, 1});
                }
            }
        }
    }

    cout << ⑤ << endl;
    return 0;
}

④ 处应填（ ）

选项

• A. d[v][0]
• B. d[v][1]
• C. d[u][0]
• D. d[u][1]

答案

C

题解

选 C：d[u][0]。

d[u][0] 表示到达点 u、还没使用免费机会时的最小费用；d[v][1] 表示到达点 v、已经使用免费机会时的最小费用。

在 if (used == 0) 中，可以把当前边 u → v 作为免费边。经过它不增加费用，所以新的费用仍是 d[u][0]。若它比 d[v][1] 小，就更新：

``cpp if (d[u][0] < d[v][1]) { d[v][1] = d[u][used]; // used == 0，即 d[u][0] pq.push({d[v][1], v, 1}); } ``