【AcWing】852. spfa判断负环
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;const int N= 1e5+10;int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N],cnt[N];//cnt存最短路径的边数
bool st[N];void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}int spfa(){//不需要初始化，求的不是距离1号点的最短路径，而是是不是存在负环。//memset初始化作用于的是求起点到终点的最短路径，而判读负环只依靠dist[j]>dist[t]+w[i]递推就可以判断。//dist只是工具数组，初值是多少都无所谓，dist不断变小才是关键。//把所有顶点都入队了，可以看成所有点都是初始点。//在第一步每个点都作为初始点走下一步时，下一步如果是正权值，那压根就不会走，下一步是负权值才会走。由于负权回路总和是负数，所以就算下一步是正权值，由前几步积累的负值的绝对值肯定会大于这个值，然后加完为负数，就能走了。一直无限循环，直到积累的边数达到判断条件。/*memset(dist,0x3f,sizeof dist);dist[1]=0;*/queue<int> q;//不能把1号点放进去，题目判断是否存在负环，并不是判断是否存在从1开始的负环。就是可能存在1号点到不了的负环。//那怎么办呢？把每个点都放到初始的点集里面。这样只要存在负环的话，就一定可以找到。for(int i=1;i<=n;i++){q.push(i);st[i]=true;}while(q.size()){int t=q.front();q.pop();st[t]=false;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(!st[j]){q.push(j);st[j]=true;}}}}return false;
}int main(){cin>>n>>m;memset(h,-1,sizeof h);for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);}if(spfa()) puts("Yes");else puts("No");return 0;
}