判负环——spfa

#单测试点有多组测试数据，注意fill手动清空

int e[M],ne[M],w[M],h[N],idx;
int d[N],cnt[N],vis[N];
//为了卡常用spfa的时候就用链式前向星
void init(){
 fill(h,h+n+1,-1);idx=0;
}
void add(int a,int b,int c){//调用之前h要全部变成-1
  e[idx]=b;w[idx]=c;
  ne[idx]=h[a];h[a]=idx++;
}
bool spfa(){ //判负环，存在返回true
  fill(d,d+n+1,inf); 
  fill(vis,vis+n+1,0);
  fill(cnt,cnt+n+1,0);
  queue<int>q; 
   for(int i=1;i<=n;i++)
    {
        q.push(i);
        vis[i]=true;
    }
  d[1]=0; 
  while(q.size()){
    int u=q.front();q.pop();vis[u]=0;
    for(int i=h[u];i!=-1;i=ne[i]){
      int v=e[i];
      if(d[v]>d[u]+w[i]){
        d[v]=d[u]+w[i];
        cnt[v]=cnt[u]+1; 
        if(cnt[v]>=n)return 1;//判边数
        if(!vis[v])q.push(v),vis[v]=1;
      }
    }
  }
  return 0;
}