你可曾听过SPFA堆优化？？？

堆优化的spfa又叫 允许多次入队的dijkstra。

没有负边的时候和dij一样，有负权边可能会被卡成指数级别。

那么这道题也是如此，只要将SPFA中的队列改成优先队列即可qwq

放代码qwq

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
long long n,m,dis[100005],head[100005],tot=1;//这里tot开始自己设为0，后来wa了一个点qwq。
long long ans,p[100005],f[100005],t[100005],k,sum;
bool vis[100005];
struct node
{
	int start,to,val;
}edge[100005];
struct cmp
{
    bool operator()(int a,int b)
    {
        return dis[a]>dis[b];
    }
};
priority_queue<int,vector<int>,cmp> q;//建堆
void add(int u,int v,int w)
{
	edge[++tot].start=v;
	edge[tot].val=w;
	edge[tot].to=head[u];
	head[u]=tot;
}
void spfa()
{
	memset(dis,0x7f,sizeof(dis));
	dis[1]=0;
	q.push(1);
	vis[1]=true;
	while(!q.empty())
	{
		int u=q.top();//这里不是q.front()！
		q.pop();
		vis[u]=false;
		for(int i=head[u];i;i=edge[i].to)
		{
			int v=edge[i].start;
			if(dis[v]>dis[u]+edge[i].val)
			{
				dis[v]=dis[u]+edge[i].val;
				p[v]=i;
				f[v]=u;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=true;
				}
			}
		}
	}
	return ;
}
int main()
{
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i<=m;i++)
	{
	    int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	spfa();
	ans=dis[n];
	int x=n;
	while(x!=1)
	{
		t[++k]=p[x];
		x=f[x];
	}
	for(int i=1;i<=k;i++)
	{
		edge[t[i]].val*=2;
		edge[t[i]^1].val*=2;
		spfa();
		sum=max(sum,dis[n]);
		edge[t[i]].val/=2;
		edge[t[i]^1].val/=2;
	}//原先这里写的太丑，参考了大佬的改成这样qwq
	cout<<sum-ans<<endl;
	return 0;
}

强烈推荐堆优化spfa qwq。。。 所以，spfa还没彻底死qwq（虽说这是披着spfa皮子的dijkstra）