AcWing 852. spfa判断负环
原题链接
简单
作者:
术
,
2021-12-30 16:08:22
,
所有人可见
,
阅读 211
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5+5;
int e[N], ne[N], h[N], w[N];
int idx;
int dist[N];
int cnt[N];
bool st[N];
int n, m;
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
bool spfa(){
queue<int> q;
//将所有点加入q,dist为虚拟源点到i的距离,cnt为虚拟源点到i所经过的边数
for(int i = 1; i <= n; i++)
q.push(i);
memset(dist, 0x3f, sizeof dist);
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true;//若虚拟源点到i的经过的边数(虚拟源点到初始x的经过的边数为0)大于等于n,则说明有n+1个点
if(!st[j]){
st[j] = true;
q.push(j);
}
}
}
}
return false;
}
int main()
{
cin>>n>>m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i++){
int a, b, c;
cin>>a>>b>>c;
add(a, b, c);
}
if(spfa()) cout<<"Yes";
else cout<<"No";
return 0;
}