【自用】关于严格次短路

19ty84 · 2025-01-21 01:32:07 · 个人记录

#include<bits/stdc++.h>
#include<queue>
using namespace std;
int n,r,p1[5002],p2[5002];
vector<pair<int,int> > G[5002]; 
priority_queue<pair<int,int> > q;
int main(){
    cin>>n>>r;
    for(int i=1;i<=n;i++)p1[i]=p2[i]=1073741823;
    for(int i=1;i<=r;i++){
        int u,v,w;
        cin>>u>>v>>w;
        G[u].push_back(make_pair(w,v));
        G[v].push_back(make_pair(w,u));
    }
    q.push(make_pair(0,1));
    p1[1]=0;
    while(!q.empty()){
        pair<int,int> pr=q.top();
        q.pop();
        int u=pr.second,z=pr.first;
        if(z>p2[u])continue;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].second,w=G[u][i].first;
            if(p1[u]+w<=p1[v]){
                p1[v]=p1[u]+w;
                q.push(make_pair(p1[v],v));
            }
            else if(p1[u]+w<p2[v]){
                p2[v]=p1[u]+w;
                q.push(make_pair(p2[v],v));
            }
            if(p2[u]+w<p2[v]){
                p2[v]=p2[u]+w;
//              q.push(make_pair(p2[v],v));
            }
        }
    }
    cout<<p2[n]<<endl;
    return 0;
} 

为什么 if(p2[u]+w<p2[v]) 不需要 q.push(make_pair(p2[v],v))？

因为前面已经执行过 if(p1[u]+w<=p1[v]) 和 else if(p1[u]+w<p2[v]) 了。如果前面两个的其中一个满足，那么自然会将 v 添加到 q 里；如果前面两个不满足，那就是说连 u 的最短路都无法更新 v 的次短路，因此 if(p2[u]+w<p2[v]) 不可能满足。