AcWing 904. 虫洞 题解（spfa求负环）

AcWing 904. 虫洞
负环就是图中存在的权值之和为负数的环，如果图中存在负环，则农夫一定能返回起点，反之一定不能，所以这是一个裸的求负环的题目。用spfa记录最短路上的边的数量，如果某条路径上边的数量大于等于n，则可以认定这条路上存在负环，返回true即可，反之返回false

#include<bits/stdc++.h>

using namespace std;

const int N = 520, M = 5210;

int T, n, m1, m2;
int h[N], ne[M], e[M], w[M], idx;
int st[N];
int dist[N];  //最短距离记录数组
int cnt[N];  //记录最短距离的边数

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

bool spfa(){
      //判断负环 
	memset(dist, 0, sizeof dist);
	memset(st, 0, sizeof st);
	memset(cnt, 0, sizeof cnt);
	
	queue<int>q;
	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; 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;  //从t到j多了一条边w[t][j] 
				if(cnt[j] >= n) return true;  //如果这个路径上的边的数量大于n，那说明存在负环，农夫一定可以回到起点
				if(!st[j]){
    
					q.push(j);
					st[j] = true;
				} 
			}
		}
	}
	return false;  //如果一直没有找到负环，说明农夫回不到起点，返回false 
}

int main()
{
    
	cin>>T;
	while(T -- ){
    
		cin>>n>>m1>>m2;
		memset(h, -1, sizeof h);
		idx = 0;  //记住初始化 
		for(int i = 0; i < m1; i ++ ){
    
			int a, b, c;
			cin>>a>>b>>c;
			//正常路径，相当于双向变 
			add(a, b, c);
			add(b, a, c);
		}
		for(int i = 0; i < m2; i ++ ){
    
			int a, b, c;
			cin>>a>>b>>c;
			add(a, b, -c);  //虫洞相当于一条负权边 
		} 
		
		if(spfa()) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	} 
	return 0;
}