特殊最短路-万卷网

题型：组合题

特殊最短路

题目背景

给定一个含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(    ①   ); // ①处待完善（注：原文①处对应初始化相关）
    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;
}

(1)．

②处应填？