路障(Roadblocks) 题解

算法分析

对每个节点同时维护从 $1$ 出发的最短路距离 $d_1[u]$ 与严格次短路距离 $d_2[u]$（满足 $d_1[u] < d_2[u]$，允许重复走边折返）。在堆优化 Dijkstra 中，用边 $(u, v, w)$ 松弛得到新距离 $nd = d + w$ 时：若 $nd < d_1[v]$，则将原 $d_1[v]$ 下移为 $d_2[v]$ 并更新 $d_1[v] = nd$ 入堆；若 $d_1[v] < nd < d_2[v]$，则更新 $d_2[v] = nd$ 入堆。最终 $d_2[N]$ 即为答案，时间复杂度 $O(R \log N)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r;
    if (!(cin >> n >> r)) return 0;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < r; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    const long long INF = (1LL << 60);
    vector<long long> d1(n + 1, INF), d2(n + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    d1[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > d2[u]) continue;
        for (auto [v, w] : g[u]) {
            long long nd = d + w;
            if (nd < d1[v]) {
                d2[v] = d1[v];
                d1[v] = nd;
                pq.push({d1[v], v});
                if (d2[v] < INF) pq.push({d2[v], v});
            } else if (nd > d1[v] && nd < d2[v]) {
                d2[v] = nd;
                pq.push({d2[v], v});
            }
        }
    }
    cout << d2[n] << "\n";
    return 0;
}