AcWing 852. spfa判断负环
原题链接
简单
作者:
梦都会空
,
2021-12-06 18:12:00
,
所有人可见
,
阅读 120
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 10000010;
int head[N],e[N],ne[N],w[N],idx;
int d[N],c[N];
bool st[N];
int n,m;
void add(int x,int y,int z)
{
e[idx]=y,w[idx]=z,ne[idx]=head[x],head[x]=idx++;
}
bool boonm()
{
queue<int> q;
for(int i=1;i<=n;i++)
{
st[i]=true;
q.push(i);
}
st[1]=true;
while(q.size())
{
int t=q.front();
q.pop();
st[t]=false;
for(int i=head[t];i!=-1;i=ne[i])
{
int j=e[i];
if(d[j]>d[t]+w[i])
{
d[j]=d[t]+w[i];
c[j]=c[t]+1;
if(c[j]>=n) return true;
if(!st[j])
{
q.push(j);
st[j]=true;
}
}
}
}
return false;
}
signed main()
{
cin>>n>>m;
memset(head,-1,sizeof head);
for(int i=0;i<m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
}
if(boonm()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}