AcWing 852. spfa判断负环
原题链接
简单
作者:
minux
,
2020-04-27 15:25:58
,
所有人可见
,
阅读 614
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define fi first
#define se second
#define INF 0x3f3f3f3f
const int N=2005;
vector<PII> G[N];
int CNT[N];
int vis[N];
int DIS[N];
int n,m;
bool SPFA(){
DIS[1]=0;
queue<int> q;
// 所有点加入到队列中
for(int i=1; i<=n; ++i) {q.push(i); vis[i]=true;}
while(!q.empty()){
int node = q.front();
q.pop();
vis[node]=false;
for(auto &v: G[node]){
if(DIS[v.fi]>DIS[node]+v.se){
DIS[v.fi]=DIS[node]+v.se;
CNT[v.fi]=CNT[node]+1;
if(CNT[v.fi]>=n) return true;
if(!vis[v.fi]){
q.push(v.fi);
vis[v.fi]=true;
}
}
}
}
return false;
}
int main(){
// SPFA算法, 加入环判定数组
memset(CNT, 0x00, sizeof CNT);
memset(vis, 0x00, sizeof vis);
memset(DIS, 0x3f, sizeof DIS);
cin>>n>>m;
int x,y,w;
while(m--){
cin>>x>>y>>w;
G[x].push_back({y, w});
}
if(SPFA()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}