【题目来源】
AcWing：852. spfa判断负环 - AcWing题库
【题目描述】
给定一个\(n\)个点\(m\)条边的有向图，图中可能存在重边和自环，边权可能为负数。请你判断图中是否存在负权回路
【输入】
第一行包含整数 \(n\) 和 \(m\)。
接下来\(m\)行每行包含三个整数 \(x,y,z\)，表示存在一条从点\(x\)到点\(y\)的有向边，边长为\(z\)
【输出】
如果图中存在负权回路，则输出Yes，否则输出No。
【输入样例】
3 3
1 2 -1
2 3 4
3 1 -4
【输出样例】
Yes
【解题思路】
【算法标签】
《AcWing 852 SPFA判断负环》 #负环判定# #spfa#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 定义常量
const int N = 2010, M = 10010, INF = 1e9; // N为节点数上限，M为边数上限，INF为无穷大// 定义图的邻接表表示
int h[N], e[M], w[M], ne[M], idx; // h数组存储每个节点的第一条边的索引，e数组存储边的终点，w数组存储边的权重，ne数组存储下一条边的索引，idx为边的计数器// 定义SPFA算法所需的数组
int dist[N], cnt[N]; // dist数组存储从起点到每个节点的最短距离，cnt数组存储每个节点入队次数
queue<int> q; // 队列用于BFS
bool st[N]; // st数组标记节点是否在队列中// 定义节点数和边数
int n, m;// 添加边的函数
void add(int a, int b, int c) {e[idx] = b, w[idx] = c; // 设置边的终点和权重ne[idx] = h[a], h[a] = idx++; // 更新邻接表
}// SPFA算法实现
bool spfa() {// 初始化所有节点的距离为无穷大，并将所有节点入队for (int i = 1; i <= n; i++) {q.push(i);st[i] = true;}// 开始BFSwhile (!q.empty()) {int nd = q.front(); q.pop(); // 取出队首节点st[nd] = false; // 标记该节点已出队// 遍历该节点的所有出边for (int i = h[nd]; i != -1; i = ne[i]) {int j = e[i]; // 边的终点// 如果通过当前边可以得到更短的距离，则更新距离并入队if (dist[j] > dist[nd] + w[i]) {dist[j] = dist[nd] + w[i];cnt[j] = cnt[nd] + 1; // 更新入队次数// 如果某个节点入队次数超过n次，说明存在负环if (cnt[j] >= n) return true;// 如果该节点不在队列中，则入队if (!st[j]) {q.push(j);st[j] = true;}}}}return false; // 未发现负环
}int main() {cin >> n >> m; // 输入节点数和边数memset(h, -1, sizeof(h)); // 初始化邻接表while (m--) {int a, b, c;cin >> a >> b >> c; // 输入边的起点、终点和权重add(a, b, c); // 添加边}// 初始化距离数组为无穷大memset(dist, INF, sizeof(dist));dist[1] = 0; // 起点到起点的距离为0// 调用SPFA算法if (spfa()) cout << "Yes"; // 存在负环else cout << "No"; // 不存在负环return 0;
}【运行结果】
3 3
1 2 -1
2 3 4
3 1 -4
Yes