06 负环判定

$SPFA$ 当中 $cnt[i]\ge n$ 就是代表有负环

vector<pair<int,int>> G[N]; //记录有向边和边权
vi dis(n + 10，INF); //记录最短路径
vi cnt(n + 10); //记录边数
vi vis(n + 1);
dis[s] = 0; 
vis[s] = 1;
queue<int> q;
q.push(s);
 
while(!q.empty()){
	int u = q.front();
	q.pop();
	vis[u] = 0;
	for(auto v : G[u]){
		if(dis[u] + v.second < dis[v.first]){
			dis[v.first] = dis[u] + v.second;
			cnt[v] = cnt[u] + 1;
			if(cnt[v] >= n) 表示存在负环，然后跳出这一整个程序
			if(vis[v.first] == 0) q.push(v.first);
			vis[v.first] = 1; 
		}
		
	}
}
 
如果没有前面跳出，那就相当于没有负环	
rep(i,1,n)cout<<(dis[i]==INF?-1:dis[i])<<" \n"[i==n];