跳转链接
https://www.acwing.com/problem/content/854/ 来源：模板题
题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。 请你判断图中是否存在负权回路。
输入格式 第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。 输出格式 如果图中存在负权回路，则输出 Yes，否则输出 No。 数据范围 1 2000 , 1 10000, 图中涉及边长绝对值均不超过 10000。 输入样例
3 3 1 2 -1 2 3 4 3 1 -4 输出样例 Yes
题解思路
参考https://www.acwing.com/solution/content/6336/
代码
cpp
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010;
int n, m, a, b, c, idx;
int h[N], w[N], e[N], ne[N], dist[N], cnt[N];
bool vis[N];
/*cnt记录每个点到起点的边数，当cnt[i] >= n 表示出现了边数>=结点数，必然有环，而且一定是负环！
vis判断当前的点是否已经加入到队列当中了；已经加入队列的结点就不需要反复的把该点加入到队列中了
就算此次还是会更新到起点的距离，那只用更新一下数值而不用加入到队列当中。
意味着，vis数组起着降低效率的作用，不在乎效率的话，去掉也可以
*/
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool spfa()
{
// 这里不需要初始化dist数组为 正无穷/初始化的原因是， 如果存在负环， 那么dist不管初始化为多少， 都会被更新
queue<int>q;
//不仅仅是1了， 因为点1可能到不了有负环的点， 因此把所有点都加入队列
for (int i = 1; i <= n; i++)
{
q.push(i);
vis[i] = true;
}
while (q.size())
{
int t = q.front();
q.pop();
vis[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;
if (!vis[j])
{
q.push(j);
vis[j] = true;
}
}
}
}
return false;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
while (m--)
{
cin >> a >> b >> c;
add(a, b, c);
}
if (spfa()) cout << "Yes";
else cout << "No";
return 0;
}
