AcWing 852. spfa判断负环
#include <bits/stdc++.h>
using namespace std;
const int N = 2005, M = 10005;
int head[N], cnt;
int n, m;
int dis[N], backup[N];
int step[N]; //到当前点最短路径跳转的步数
bool st[N];
struct
{
int v, w;
int nxt;
} edges[M];
int spfa()
{
memset(dis, 0x3f, sizeof dis);
memset(st, 0, sizeof st);
memset(step, 0, sizeof step);
queue<int> q;
for (int i = 1; i <= n; ++i) {
dis[i] = 0;
q.push(i);
st[i] = true;
step[i] = 1;
}
//设置一个到所有点距离都为0的超级源点,若不存在负环,则求所有点的最短路时最多经过的步数不超过n步
while (!q.empty())
{
int f = q.front();
q.pop();
st[f] = false;
for(int e = head[f]; e != 0; e = edges[e].nxt) {
int u = f, v = edges[e].v, w = edges[e].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
step[v] = step[u] + 1;
if (!st[v]) {
q.push(v);
st[v] = true;
}
if (step[v] > n)
return 1;
}
}
}
return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("D:/VS CODE/C++/in.txt", "r", stdin);
freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
cin >> n >> m;
for (int i = 0; i < m; ++i)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
edges[++cnt].nxt = head[u];
edges[cnt].v = v;
edges[cnt].w = w;
head[u] = cnt;
}
if (spfa())
printf("Yes");
else
printf("No");
fclose(stdin);
fclose(stdout);
return 0;
}