ACwing（基础）--- SPFA（判负权回路）

SPFA判断图中是否存在负环

• 时间复杂度是一般O(m),最坏：（nm）

转载自小呆呆大佬

算法分析：使用spfa解决是否存在负环问题

• 1、dist[x] 记录当前1到x的最短距离
• 2、cnt[x] 记录当前最短路的边数，初始每个点到1号点的距离为0，只要它能走n步，即cnt[x] >= n,则表示该图中一定存在负环，由于从1到x至少经过n条边时，则说明图中至少有n+1个点，表示一定有点重复使用
• 3、若dist[j]>dist[t]+w[i],则表示从t点走到j点能够让权值变少，因此对点j进行更新，并且对应cnt[j]=cnt[t]+1,往前走一步

注意：不用初始化dist数组，因为是不是判断从1开始的负环

#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define mm(a,x) memset(a,x,sizeof a)
#define inf 0x3f3f3f3f

using namespace std;

const int N = 1e5+10;

int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N],vis[N],cnt[N];

void add(int a,int b,int c){
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int spfa(){
	queue<int> q;
	for(int i=1;i<=n;i++){
		vis[i]=1;
		q.push(i);
	}
	while(q.size()){
		int t = q.front();
		q.pop();
		vis[t]=0;
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];
			if(dist[j]>dist[t]+w[i]){
				dist[j]=dist[t]+w[i];
				cnt[j] = cnt[t] +1;
				if(cnt[j]>=n) return true;
				if(!vis[j]){
					q.push(j);
					vis[j]=1;
				}
			}
		}
	}
	return false;
}
int main(){
	scanf("%d%d",&n,&m);
	mm(h,-1);
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}

	if(spfa()) puts("Yes");
	else puts("No");
	return 0;
}