Roadblocks

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1423 字

Dijkstra同步维护最短路与严格次短路

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1498
// 题意：无向图求 1 到 N 的严格第二短路长度，允许重复经过道路，长度必须大于最短路且不大于其他所有路径。
// 思路：Dijkstra 同时维护最短 d1 与严格次短 d2，松弛时新距离小于 d1 就把原 d1 下移到 d2，介于 d1 与 d2 之间则更新 d2。
// 复杂度：O(R log N) 时间 / O(N+R) 空间
// 易错点：次短必须严格大于最短，等于 d1 的距离不能更新 d2，否则会把另一条并列的最短路误当成答案。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
const int INF = 0x3f3f3f3f;
struct Edge{
    int to, w;
};
vector<Edge> adj[MAXN];
int d1[MAXN];
int d2[MAXN];
int main(){
    int n, r;
    if(!(cin >> n >> r)) return 0;
    for(int i = 0; i < r; i++){
        int a, b, d;
        cin >> a >> b >> d;
        adj[a].push_back({b, d});
        adj[b].push_back({a, d});
    }
    for(int i = 1; i <= n; i++) d1[i] = d2[i] = INF;
    d1[1] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 1});
    while(!pq.empty()){
        int du = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if(du > d2[u]) continue;
        for(size_t i = 0; i < adj[u].size(); i++){
            int v = adj[u][i].to;
            int nd = du + adj[u][i].w;
            if(nd < d1[v]){
                d2[v] = d1[v];
                d1[v] = nd;
                pq.push({d1[v], v});
            }
            else if(nd > d1[v] && nd < d2[v]){
                d2[v] = nd;
                pq.push({d2[v], v});
            }
        }
    }
    cout << d2[n] << '\n';
    return 0;
}

Roadblocks

正文

一本通·提高篇的其它内容