# 【最短路】SPFA## 题目描述给定一个 $n$ 个点的有向图请求出图中是否存在从顶点 $1$ 出发能到达的负环。负环的定义是：一条边权之和为负数的回路。## 输入格式本题单测试点有多组测试数据。输入的第一行是一个整数 $T$表示测试数据的组数。对于每组数据的格式如下：第一行有两个整数分别表示图的点数 $n$ 和接下来给出边信息的条数 $m$。接下来 $m$ 行每行三个整数 $u v w$。-

算法思路

本题要求是否存在负环，可以使用 SPFA 算法（最短路径快速算法）进行求解。

SPFA 是 Bellman-Ford 算法的优化，原理是采用队列对 Bellman-Ford 算法进行优化，使得每个节点只被遍历一次。

具体来说，SPFA 维护一个队列，初始时将起点入队。然后在队列中取节点 $u$，遍历 $u$ 的所有出边，如果 $u$ 的某个出边 $(u, v)$ 使得从起点到 $v$ 的最短路可以被更新，即 $dis[v] > dis[u] + w(u, v)$，则将 $v$ 入队。这个过程不断执行，直到队列为空。

如果在这个过程中某个节点 $v$ 被重复入队超过 $n$ 次，则说明存在负环。因为一个无限大的负环可以使得从负环中的任意节点都可以到达其它任意节点，而因为负环的存在，从起点到达负环中的任意节点的路径权值可以不断地变小。

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 2010, M = 6010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa()
{
    memset(dist, 0x3f, sizeof dist);
    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
        cnt[i] = 1;
    }
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; ~i; 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 (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n >> m;
        memset(h, -1, sizeof h);
        idx = 0;
        while (m -- )
        {
            int a, b, c;
            cin >> a >> b >> c;
            if (c >= 0) add(a, b, c), add(b, a, c);
            else add(a, b, c);
        }

        if (spfa()) puts("YES");
        else puts("NO");
    }

    return 0;
}

Python 代码

def add(a, b, c):
    e.append(b)
    w.append(c)
    ne.append(h[a])
    h[a] = len(e) - 1

def spfa():
    dist = [0x3f3f3f3f] * (n + 1)
    cnt = [1] * (n + 1)
    st = [False] * (n + 1)

    q = [i for i in range(1, n + 1)]
    for i in q: st[i] = True

    while q:
        t = q.pop(0)
        st[t] = False

        i = h[t]
        while i != -1:
            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 not st[j]:
                    q.append(j)
                    st[j] = True

            i = ne[i]

    return False

T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    h = [-1] * (n + 1)
    e, ne, w = [], [], []
    for _ in range(m):
        a, b, c = map(int, input().split())
        if c >= 0: add(a, b, c), add(b, a, c)
        else: add(a, b, c)

    if spfa(): print('YES')
    else: print('NO')
``