增加一个cnt数组,表示当前最短路边的个数
cnt[x]=cnt[t]+1
当cnt[x]>=n时,意味着从1到x共经过了n条边,即n+1个点,但总共只有n个点,所以必定有环
dist数组仍表示为起点到该点的最短路,
以下参考: https://www.acwing.com/solution/content/92094/
为什么dist为0
为什么cnt[i]>n时有负环
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int idx,e[N],ne[N],h[N],w[N];
int n,m;
int dist[N];
bool used[N];
int q[N],rear=-1,front;
int cnt[N];
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
// memset(dist,0x3f,sizeof dist);
// dist[1]=0; 不需要初始化了
// used[1]=true;
// q[++rear]=1;一开始不能只把一号点加进去,因为负环可能不在1号点,要把所有点都加进去
for(int i=1;i<=n;i++)
{
used[i]=true;
q[++rear]=i;
}
while(rear>=front)
{
int t=q[front++];
used[t]=false;
for(int i=h[t];i!=-1;i=ne[i])
{
int k=e[i];
if(dist[k]>dist[t]+w[i])
{
dist[k]=dist[t]+w[i];
cnt[k]=cnt[t]+1;
if(cnt[k]>=n)
{
puts("Yes");
return 0;
}
if(!used[k])
{
q[++rear]=k;
used[k]=true;
}
}
}
}
puts("No");
return 0;
}