次短路

mengnn · 2025-07-09 15:55:35 · 个人记录

次短路模板题

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
struct node{
    int y;
    long long v;
    node(int _y,long long _v){y=_y;v=_v;};
};
struct P{
    long long dist;
    int id;
    bool operator<(P A)const{
        if (dist==A.dist)
            return id>A.id;
        return dist>A.dist;
    }
};
int n,m;
long long dist[N][2];
vector<node> edge[N];
priority_queue<P> q;
inline long long Dijkstra(){
    memset(dist,127,sizeof(dist));
    q.push({dist[1][0]=0,1});
    while (!q.empty()){
        P t=q.top();q.pop();
        if (t.dist>dist[t.id][1]) continue;
        for (auto i:edge[t.id])
            if (t.dist+i.v<dist[i.y][0]){
                dist[i.y][1]=dist[i.y][0];
                q.push({dist[i.y][0]=t.dist+i.v,i.y});
            }else if (t.dist+i.v<dist[i.y][1]&&
                      t.dist+i.v>dist[i.y][0])
                q.push({dist[i.y][1]=t.dist+i.v,i.y});
    }return dist[n][1];
}
int main(){
    cin>>n>>m;
    while (m--){
        int x,y;long long z;
        cin>>x>>y>>z;
        edge[x].push_back({y,z});
        edge[y].push_back({x,z});
    }cout<<Dijkstra();
    return 0;
}

第33行非常重要必不可少，这一行保证了次短路的严格次小性