CSP-S 提高级 · CSP 2025 提高级第一轮 第 19 题

三、完善程序（单选题，每小题 3 分，共计 30 分）

（特殊最短路）给定一个含 $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 + 

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这道题考分层图最短路。拿到题先别想复杂，核心就是给每个点加个状态：0 表示还没用过免费边，1 表示已经用过了。然后跑两遍 Dijkstra，一层层更新距离，最后取终点两个状态的最小值。

很多学生容易把免费边当成‘可以随便用一次’，忽略了题目强调的‘至多一条’且‘第一次免费、之后正常’。还有个高频坑是状态转移时搞混了：用免费边那次，费用应该是 d[u][0] 直接加 0 跳到 d[v][1]，而不是 d[u][0]+w。另外，Dijkstra 的剪枝条件写错成 d[u][!used] 或者 INF 都会导致死循环或错误结果，一定要对应当前状态 used 去查 d[u][used]。

考察知识点

图论算法 — 最短路径 / 分层图最短路

概念定义

• 分层图最短路：把原图的每个状态复制成一层，层内正常走边，层间走特殊边。
• 本题状态：d[u][0] 表示还没用过免费边时到 u 的最小费用；d[u][1] 表示已经用过免费边时到 u 的最小费用。

命题视角

命题人爱考这种‘带限制的最短路’，比如免费边、打折边、次数限制等。坑点通常藏在转移细节里：免费边只对第一次生效，用了之后费用要正常加；而且免费边只能用在还没用过的时候（used=0），用了之后只能去 used=1 那层，不能再回头。这种单向状态机是 Dijkstra 能跑通的关键。

思考心法

拿到题先想： 1. 状态怎么定义？显然要记录‘是否用过免费边’，所以 d[u][0/1]。 2. 转移分几种情况？ - 不用免费边：d[v][used] = min(d[v][used], d[u][used] + w) - 用免费边（仅当 used=0）：d[v][1] = min(d[v][1], d[u][0]) 3. 初始化和答案？起点 s 没走过免费边，d[s][0]=0；终点答案取 min(d[t][0], d[t][1])。 4. 算法选择？边权非负，用 Dijkstra，priority_queue 存 (dist, u, used)。

逐空推演

① 初始状态：起点 s，还没用过免费边，used=0，距离 0。所以填 0。 ② Dijkstra 剪枝：弹出当前状态 (dist, u, used)，如果 dist 比已经算过的 d[u][used] 大，说明这是旧状态，跳过。填 d[u][used]。 ③ 不用免费边的转移：当前状态是 used，走边 w 到 v，新距离是 d[u][used]+w，更新 d[v][used]。填 d[v][used]。 ④ 用免费边的转移：只有当 used=0 时才可能用免费边。此时费用是 d[u][0]（免费，加 0），更新 d[v][1]。比较条件是 d[u][0] < d[v][1]。填 d[u][0]。 ⑤ 输出答案：终点 t 可能没用过免费边，也可能用过了，取两者最小。填 min(d[t][0], d[t][1])。

避坑指南

• 免费边次数限制：题目说‘至多一条’，所以用了之后不能再用。代码里用 used 标记状态，一旦 used=1，就再也触发不了‘免费边’那条转移，天然满足限制。
• 免费边生效时机：必须是‘第一次经过’免费，之后正常计费。代码里用免费边时，是从 d[u][0] 直接跳到 d[v][1]，费用没加 w；而后续从 d[v][1] 出发走任何边都会加 w，完全符合题意。
• Dijkstra 剪枝细节：很多人会写成 dist > d[u][!used] 或者 INF，这是错的。因为 d[u][0] 和 d[u][1] 是两个独立的最短距离，不能混用。必须用当前状态对应的值 d[u][used] 来剪枝，否则可能把已经处理过的状态重新放回队列，导致死循环或错误结果。
• 状态转移方向：用免费边时，只能从 used=0 跳到 used=1，不能反过来。代码里 if (used == 0) 保证了这一点，这是单向状态机的核心。

考频与趋势

• 基础算法：题库共考过 30 题，覆盖 3 个考试级别（2007-2025）；逐年分布：2007 年 2 题、2008 年 1 题、2009 年 4 题、2010 年 4 题、2011 年 5 题、2012 年 1 题、2013 年 1 题、2014 年 2 题、2016 年 1 题、2019 年 1 题、2021 年 4 题、2024 年 2 题、2025 年 2 题；分赛事：NOIP 提高组 初赛 13 题、CSP 提高级 9 题、NOIP 普及组 初赛 8 题。
• 图论算法：题库共考过 26 题，覆盖 3 个考试级别（2015-2026）；逐年分布：2015 年 2 题、2016 年 1 题、2017 年 1 题、2019 年 1 题、2021 年 1 题、2024 年 1 题、2025 年 2 题、2026 年 5 题、null 年 12 题；分赛事：CSP 入门级 14 题、CSP 提高级 8 题、NOIP 提高组 初赛 4 题。
• 最短路径：题库共考过 35 题，覆盖 7 个考试级别（2008-2026）；逐年分布：2008 年 2 题、2011 年 1 题、2012 年 1 题、2013 年 1 题、2014 年 1 题、2015 年 2 题、2016 年 1 题、2018 年 1 题、2019 年 1 题、2020 年 1 题、2021 年 1 题、2024 年 6 题、2025 年 7 题、2026 年 7 题、null 年 2 题；分赛事：GESP 八级 17 题、NOIP 提高组 初赛 9 题、CSP 提高级 5 题、GESP 六级 1 题、NOIP 普及组 初赛 1 题、GESP 五级 1 题、GESP 七级 1 题。

预测

从数据看，最短路径在 2024-2026 年考频明显上升（2024 年 6 题、2025 年 7 题、2026 年 7 题），且分层图/状态压缩类题目在 CSP 提高级和 NOIP 提高组初赛中都有一定比例。未来可能继续考察带限制的最短路（如多次免费、打折次数、路径长度限制等），或者结合其他图论模型（如最小生成树 + 最短路）。暂无足够依据预测具体题型，但建议重点复习分层图 Dijkstra 模板和状态转移的严谨性。