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

题目

（特殊最短路）给定一个含 $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. 0
• B. 1
• C. -1
• D. false

答案

A

题解

应选 A．0。

used_freebie 表示是否已经用过免费机会：

• 0：还没用过；
• 1：已经用过。

初始时位于起点 s，还没有经过任何边，因此免费机会尚未使用。对应 d[s][0] = 0，入队应写：

``cpp pq.push({0, s, 0}); ``

这里的三个值分别表示：当前费用、所在节点、是否已使用免费机会。

不过，严格按 C++ 语法，D．false 也正确：它会自动转换为整数 0，效果与 A 完全相同。因此若本题是单选题，选项设置存在歧义，预期答案应为 A。