学习心得 - 算法 - 次短路

ExFish · 2025-06-06 13:00:59 · 算法·理论

算一个 ABC 比较常用的工具吧。

（严格）方法 1 Astar + Dij

额这个就是用的 k 短路改的，k=2。

这个不用代码。

（严格）方法 2 Dij 维护信息

就是在 Dij 的时候多维护一个次短路然后更新即可。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
vector<pair<int,int>>e[N];
int n,r,dis[N][2];
struct dij{
    int p,d;
};
bool operator<(dij x,dij y){
    return x.d>y.d;
}
bool vis[N];
priority_queue<dij>q;
signed main(){
    cin>>n>>r;
    for(int i=1;i<=r;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1][0]=0;
    q.push({1,0});
    while(q.size()){
        auto f=q.top();
        q.pop();
        vis[f.p]=1;
        for(auto v:e[f.p]){
            if(f.d+v.second<dis[v.first][0]){
                dis[v.first][1]=dis[v.first][0];
                dis[v.first][0]=f.d+v.second;
                q.push({v.first,dis[v.first][0]});
            }
            if(f.d+v.second<dis[v.first][1]
            &&f.d+v.second>dis[v.first][0]){
                dis[v.first][1]=f.d+v.second;
                q.push({v.first,dis[v.first][1]});
            }
        }
    }
    cout<<dis[n][1];
    return 0;
}

（非严格）方法 3 替换边

从起点 s 与 t 各搜一次，然后枚举一条不在原最短路径上的边做替换。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<array<int,3>>e[N];
int n,m,dis[N][2],fir;
pair<int,int>pre[N];
vector<array<int,3>>g;
struct dij{
    int p,d;
};
bool operator<(dij x,dij y){
    return x.d>y.d;
}
bool vis[3*N];
priority_queue<dij>q;
void rep(){
    int p=n;
    while(p){
        vis[pre[p].second]=1;
        p=pre[p].first;
    }
    return;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w,i});
        g.push_back({u,v,w});
        e[v].push_back({u,w,i});
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1][0]=0;
    q.push({1,0});
    while(q.size()){
        auto f=q.top();
        q.pop();
        for(auto v:e[f.p])if(f.d+v[1]<dis[v[0]][0]){
            dis[v[0]][0]=f.d+v[1];
            pre[v[0]]={f.p,v[2]};
            q.push({v[0],dis[v[0]][0]});
        }
    }
    if(dis[n][0]==dis[0][0])
        return cout<<-1,0;
    dis[n][1]=0;
    q.push({n,0});
    while(q.size()){
        auto f=q.top();
        q.pop();
        for(auto v:e[f.p])if(f.d+v[1]<dis[v[0]][1]){
            dis[v[0]][1]=f.d+v[1];
            q.push({v[0],dis[v[0]][1]});
        }
    }
    rep();
    int ans=dis[0][0];
    for(int i=1;i<=m;i++)if(!vis[i]){
        int u=g[i-1][0],v=g[i-1][1],w=g[i-1][2];
        ans=min(ans,dis[u][0]+w+dis[v][1]);
        ans=min(ans,dis[v][0]+w+dis[u][1]);
    }
    if(ans==dis[0][0])  
        return cout<<-1,0;
    cout<<dis[n][0]+ans;
    return 0;
}