AcWing 852. spfa判断负环
原题链接
简单
作者:
呼和
,
2019-08-30 00:03:33
,
所有人可见
,
阅读 989
一个神器的题。
不需要你去判断是否能够到终点,只要你能够判断是否能够有负环就可以了。
看别人思路,自己写代码,能够深入了解代码思路。
/*****************************************
Problem Name :
******************************************/
#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define LL long long
const int N = 100010;
const int Inf = 0x3f3f3f;
int head[N],vis[N],dis[N],net[N],to[N],data[N],idx = 1,sum[N];
int n , m;
void add(int x, int y , int z)
{
data[idx] = z;
to[idx] = y;
net[idx] = head[x];
head[x] = idx++;
}
bool spfa()
{
bool flag = 0;
queue<int> p;
for(int i = 1 ; i <= n ; i++)
{
p.push(i);
dis[i] = 0;
vis[i] = i;
sum[i]++;
}
while(!p.empty())
{
int t = p.front();
vis[t] = 0;
p.pop();
for(int i = head[t] ; i ; i = net[i])
{
int j = to[i];
if(dis[j] > dis[t] + data[i])
{
dis[j] = dis[t] + data[i];
if(!vis[j])
{
vis[j] = 1;
p.push(j);
if(j == n)
flag = 1;
sum[j]++;
if(sum[j] > n)
return false;
}
}
}
}
return true;
}
int main()
{
memset(dis,Inf , sizeof(dis));
cin >> n >> m;
while(m--)
{
int x, y,z;
cin >> x >> y >> z;
add(x,y,z);
}
if(!spfa())
cout << "Yes\n";
else
cout << "No" << endl;
}