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

题目

（特殊最短路）给定一个含 $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[t][1]
• B. d[t][0]
• C. min(d[t][0], d[t][1])
• D. d[t][0] + d[t][1]

答案

C

题解

选 C：min(d[t][0], d[t][1])。

这里把每个点分成两种状态：

• d[u][0]：到达点 u，尚未使用免费机会的最小费用。
• d[u][1]：到达点 u，已经使用免费机会的最小费用。

题目说的是“至多选择一条免费边”，所以到达终点时，既可以没使用免费机会，也可以已经使用。取两种情况的较小值：

``cpp cout << min(d[t][0], d[t][1]) << endl; ``

这就是分层最短路：正常走边时，状态不变、费用加 w；使用免费机会时，从状态 0 转到状态 1、费用不增加。进入状态 1 后，所有边都按原价计费。