SPFA求负环&SPFA最短路

前言

关于SPFA，他死了。

但是，不得不承认，SPFA其实挺好用的。

基本变量

• 一个邻接表（这里仅提供代码，具体思路不讲）

• 一个队列queue<int> q

• 点数$n$和边数$m$

• 一个源点$s$

• 一个数组$vis$，$vis_i$代表$i$是否在队里面

• 一个数组$c$，$c_i$代表$i$入队几次了

思路

我们考虑如下有向图，求$1$到$3$的最短路。

3 3
1 2 -1
2 3 2
3 1 -3

那么，$1$到$3$的最短路是$-1+2=1$吗？

当然不是。

其实$1$到$3$的最短路是$-1+2-3-1+2-3+........$

原因显然，因为图中有一个环即$1-2-3-1$，它的权值是$-1+2-3=-2$，所以你在上面走的越多，它的路程越小，自然你要在上面走$\infty$圈，最终答案为$-\inf$。

那么，怎么打破这个怪圈呢？

显然如果真的有一个负环，那么在他松弛了$n-1$轮以后还能再松弛，那么说明肯定有一个奇奇怪怪的点，它连着一个负权回路，说明这个图有问题，无解。

那么就真的没什么好说的了，时间复杂度$O(km)(k$平均情况下$=2$，在稠密图下最坏$=n)$，真 的 好 快 啊。

最后，如果有最短路的话，那么$dis_i$就是$s$到$i$的最短路。

代码

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=100001,inf=0x3f3f3f3f;
const int daynum[]={114514,31,28,31,30,31,30,31,31,30,31,30,31};
const db E=2.718281828459,pi=acos(-1.0),eps=0.0000000001;
inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
struct bian{
	ll next,to,w;
	bian(){
		w=0;
		next=0;
	}
}e[N];
ll head[N],totm;
void add(ll s,ll ed,ll www){
	e[++totm].next=head[s];
	e[totm].to=ed;
	e[totm].w=www;
	head[s]=totm;
}
ll n,m,cruelm,s=1,t,d[N],p[N],c[N];
queue<ll> q;
bool vis[N],flag;
bool spfa(int s){
	q.push(s);vis[s]=1;
	c[s]++;
	d[s]=0;
	while(q.size()){
		int k=q.front();
		vis[k]=0;
		q.pop();
		for(int i=head[k];i;i=e[i].next){
			int v=e[i].to;
			if(d[v]>e[i].w+d[k]){
				d[v]=e[i].w+d[k];
				c[v]++;
				if(c[v]>=n) return 1;
				if(vis[v]==0){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;t=read();
	while(t--){
		ms(head,0);
		ms(vis,0);
		ms(c,0);
		ms(d,0x3f);
		n=read(),cruelm=read();	
		totm=1;
		fs(i,1,cruelm,1){
			int u,v,w;
			u=read(),v=read(),w=read();
			if(w>=0){
				m+=2;
				add(u,v,w);
				add(v,u,w);
			} 
			else{
				m++;
				add(u,v,w);
			} 
		}
		totm--;
		if(!spfa(1)) puts("NO");
		else puts("YES");
	}
	return 0;
}