AcWing 361. Sightseeing cow problem solution (SPFA seeking positive ring)

AcWing 361. Sightseeing cows

According to the formula in the figure , What this problem asks is to have a positive ring , So we are looking for the longest path , therefore if The judgement sentence in determines whether a longer boundary value can be found

#include<bits/stdc++.h>

using namespace std;

const int N = 1010, M = 5210;

int h[N], ne[M], e[M], w[M], idx;
int n, m;
double dist[N];
int wf[N];
bool st[N];
int cnt[N];  // Record edges  

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

bool check(double mid){
    
	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] + wf[t] - mid * w[i]){
      // What is required is a positive ring , So it's the longest way  
				dist[j] = dist[t] + wf[t] - mid * 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;
	
	for(int i = 1; i <= n; i ++ ) cin>>wf[i];
	
	memset(h, -1, sizeof h);
	for(int i = 0; i < m; i ++ ){
    
		int a, b, c;
		cin>>a>>b>>c;
		add(a, b, c);
	}
	
	double l = 0, r = 1e6;
	while(r - l > 1e-4){
    
		double mid = (l + r) / 2;
		if(check(mid)) l = mid;  // This value can , You can try to find a larger value 
		else r = mid;   // This value is not good , Looking for a smaller value 
	}
	printf("%.2lf\n", r);
	return 0;
}