AcWing 904. Wormhole solution (SPFA for negative rings)

AcWing 904. Wormhole
A negative ring is a ring in which the sum of the weights in the graph is negative , If there is a negative ring in the graph , Then the farmer must be able to return to the starting point , On the contrary, it must not , So this is a naked problem of finding negative rings . use spfa Record the number of edges on the shortest path , If the number of edges on a path is greater than or equal to n, Then it can be determined that there is a negative ring on this road , return true that will do , Instead, return to 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];  // Shortest distance record array 
int cnt[N];  // Record the number of sides of the shortest distance 

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

bool spfa(){
      // Judge negative loop  
	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;  // from t To j One more side w[t][j] 
				if(cnt[j] >= n) return true;  // If the number of edges on this path is greater than n, That means there is a negative ring , The farmer must be able to return to the starting point 
				if(!st[j]){
    
					q.push(j);
					st[j] = true;
				} 
			}
		}
	}
	return false;  // If you haven't found a negative ring , It means that the farmer cannot return to the starting point , return false 
}

int main()
{
    
	cin>>T;
	while(T -- ){
    
		cin>>n>>m1>>m2;
		memset(h, -1, sizeof h);
		idx = 0;  // Remember to initialize  
		for(int i = 0; i < m1; i ++ ){
    
			int a, b, c;
			cin>>a>>b>>c;
			// Normal path , Equivalent to Bidirectional Transformation  
			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);  // Wormhole is equivalent to a negative weight edge  
		} 
		
		if(spfa()) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	} 
	return 0;
}