完善程序（一） 1-6题 组合题 特殊最短路 题目背景 给定一个含N个点、M条边的带权无向图，边权非负。起点为S，终点为T。对于一条S到T的路径，可以在整条路径中，至多选择一条边作为“免费边”：当第一次经过这条被选中的边时，费用视为0；如果之后再次经过该边，则仍按其原始权重视计费。点和边均允许重复经过。求从S到T的最小总费用。 以下代码求解了上述问题。试补全程序。 include include include include 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 > adj(n + 1); for (int i = 0; i > u >> v >> w; adj[u].push_back( { v, w } ); adj[v].push_back( { u, w } ); } vector > d(n + 1, vector (2, INF)); priority_queue , greater > pq; d[s][0] = 0; pq.push( ① ); // ①处待完善（注：原文①处对应初始化相关） 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; // 情况1：不使用免费边 if (d[v][used] > ③ + w) { // ③处待完善 d[v][used] = d[u][used] + w; pq.push( { d[v][used], v, used } ); } // 情况2：使用免费边（仅当未使用过） if (used == 0 && d[v][1] > ④ + 0) { // ④处待完善 d[v][1] = d[u][0] + 0; pq.push( { d[v][1], v, 1 } ); } } } cout << ⑤ << endl; // ⑤处待完善 return 0; }
正确答案：完善程序①答案：{0,s,0}（初始dist=0、起点s、未用免费边）。核心：免费边最短路初始化。
试卷来源：2025 CSP-S提高级（第一轮）C++真题