P2865[USACO06NOV]RoadblocksG/【模板】次短路[数据库教程]

Z时代
2024-01-10
分类：综合

database

~~不是可持久化可并堆的事么~~

在spfa/dij的不等式中间加一个判断，看他能不能更新最短路/次短路。

~~这题不卡spfa是！！！~~

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
vector<pair<int,int> > e[maxn];
int n,m;
int dis[maxn][2];
bool vis[maxn];
void spfa(int s){
	memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[s][0]=0,vis[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(auto E:e[u]){
            int v=E.first,w=E.second;
            if(dis[v][0]>dis[u][0]+w){//最短路更新
                dis[v][1]=dis[v][0];
                dis[v][0]=dis[u][0]+w;
                if(!vis[v])vis[v]=1,q.push(v);
            }
            if(dis[v][1]>dis[u][0]+w&&dis[v][0]<dis[u][0]+w){//次短路更新
                dis[v][1]=dis[u][0]+w;
                if(!vis[v])vis[v]=1,q.push(v);
            }  
            if(dis[v][1]>dis[u][1]+w){//必然不能更新最短路，因为若能更新，已经被该节点最短路更新力
                dis[v][1]=dis[u][1]+w;
                if(!vis[v])vis[v]=1,q.push(v);
            }
        }
    }
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,w;
		cin>>x>>y>>w;
		e[x].push_back(make_pair(y,w));
		e[y].push_back(make_pair(x,w));
	}
    spfa(1);
    cout<<dis[n][1];
	return 0;
}