m 个约束条件,第 j 个约束条件有三个整数_u_,v,w,表示a_u−a_v≤w
请判断是否至少存在一组 _a_的值满足上述条件。
将起点入队,每次从队列里取一个点,尝试更新(松弛)与这个点连接的所有点的最短路径长度。如果松弛成功,那么将这个点入队(当然,如果队列里已经有了,那就没必要再入队了。用一个数组记录这个数是否已经在队列里了)。
对于负环,SPFA会对他反复松弛,使最短路变小。所以我们只要记录一下每个节点松弛的次数,如果某个点的松弛次数>n了,那肯定是有负环了。
#include<iostream>
#include<queue>
#include<cstring>
#define N 51000
using namespace std;
int v[N], w[N], nex[N];
int d[N], cnt[N], first[N];
bool vis[N]; int t;
int n,m;
void add(int x, int y, int z){
t++;
nex[t] = first[x];
first[x] = t;
v[t] = y;
w[t] = z;
}
bool SPFA(int s){
int x, y, i, j;
queue<int>q;
memset(d, 0x3f, sizeof(d));
memset(vis, false, sizeof(vis));
while (!q.empty()) q.pop();
d[s] = 0;
cnt[s] = 1;
q.push(s);
vis[s] = true;
while (!q.empty()){
x = q.front();
q.pop();
vis[x] = false;
for (i = first[x]; i; i = nex[i]){
y = v[i];
if (d[y] > d[x] + w[i]){
d[y] = d[x] + w[i];
cnt[y] = cnt[x] + 1;
if (cnt[y] > n)
return false;
if (!vis[y]){
q.push(y);
vis[y] = true;
}
}
}
}
return true;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> b >> a >> c;
add(a, b, c);
}
d[n + 1] = 0;
for (int i = 1; i <= n; i++) add(n + 1, i,0);
if (SPFA(n+1))
cout << "YES";
else
cout << "NO";
}