题目描述
blablabla
样例
blablabla
可以这样理解, 当我们求单源的是时候会把d[1]初始化为0,并且放进队列,来更新可以到达它的结点;
现在问图中有没有负权环,图可能不连通,我们不知道是哪个点可以到哪个负权,所以每个点i都初始化d[i]=0;
然后放进队列,做和单源点一样的操作。
C++ 代码
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], w[N], ne[N], idx, n, m;
int d[N], cnt[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
bool spfa()
{
//不用初始化,因为d[]默认为0;
queue<int> q;
for(int i = 1; i <= n; i++) //每个点都放进队列
{
st[i] = true;
q.push(i);
}
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(d[j] > d[t] + w[i])
{
d[j] = d[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true; //对于n个点如果没有环的话,那么只会有n-1条边;由于我们只在
if(!st[j]) // if(d[j] > d[t] + w[i])条件下更新,那么如果出现环,
{ //这个环一定是可以减小距离的;即负环;
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main()
{
cin>> n >> m;
memset(h, -1, sizeof h); //一定要初始化链表头节点;!!!!!!!!!!!
int a, b, c;
for(int i = 0; i < m; i++)
{
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
if( spfa() ) cout<< "Yes";
else cout<< "No";
return 0;
}