两次最短路题解

求第 k 短路一般使用 A* 算法或者可持久化可并堆，对于次短路有特殊解。枚举每一条不在最短路上的边并计算讲将这条边加上的最短路。因为如果想要求次短路，必须有至少一条不在最短路上的边。从起点和终点分别跑一次最短路，辅助计算以包含某条边的最短路。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,cnt,head[200005],dis[5005],minn=2e9,dis2[5005];
bool inq[5005];
struct node{
int from,next,to,w;
}tu[200005];
void add(int u,int v,int w){
    tu[++cnt].to=v;
    tu[cnt].from=u;
    tu[cnt].w=w;
    tu[cnt].next=head[u];
    head[u]=cnt;
}
void spfa(int s,int a[]){
	memset(inq,0,sizeof(inq));
	queue<int>q;
	a[s]=0;
	q.push(s);
	inq[s]=1;
	while(!q.empty()){
		int tmp=q.front();
		q.pop();
		inq[tmp]=0;
		for(int i=head[tmp];i;i=tu[i].next){
			if(tu[i].w+a[tu[i].from]<a[tu[i].to]){
				a[tu[i].to]=tu[i].w+a[tu[i].from];
				if(!inq[tu[i].to]){
					q.push(tu[i].to);
					inq[tu[i].to]=1;
				}
			}
		}
	}
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=1;i<=n;++i)dis[i]=dis2[i]=1e18;
    spfa(1,dis);
    spfa(n,dis2);
    for(int i=1;i<=cnt;++i){
        int u=tu[i].from,v=tu[i].to,w=tu[i].w;
        if(dis[u]+w+dis2[v]>dis[n])minn=min(dis[u]+w+dis2[v],minn);
    }
    cout<<minn;
    return 0;
}