RT， 源码：

题目中给出的负环定义：

> 一条边权之和为负数的回路。

负环自然用SPFA来判（Dijstra甚至不能处理有负权边的图，[为什么](https://blog.csdn.net/u012677715/article/details/79346113)）。
而未用队列优化的[Bellman-ford](https://blog.csdn.net/anlian523/article/details/80953767)复杂度为 $O(n·e)$，不是我们能接受的。

**SPFA能判断负权环得益于其的松弛操作。**
在SPFA中，我们跟新最短路的条件为$dist[u]>dist[v]+len[v][u]$。即原点通过当前已知路径从一节点到达新的节点的距离小于原点直接从已知路径到达新的节点的距离。跟新完成后，由于新的节点可能更新出一条更优路径，就放入队中（没入队的话）。此称为一次松弛。

在正常的情况下，一个点入队最多次为$n-1$，原因我们可以类比Bellman-ford：在Bellman-ford的迭代过程中，每迭代一次就最少会求出一个点到源点的最短路。也就是说，每个点最多会被迭代$n-1$次,换成了SPFA，就是每个点最多会入队$n-1$次。我们就可以运用这点来判断负环。

如果存在负环，意味着这个环将不断跟新，迭代的次数也将无穷无尽。那我们用一个$intot[]$数组来记录每个点的入队次数（也就是迭代次数）。当某个点的入队次数大于等于 $n$ 时，即意味着存在负环了。

下面是代码。

预览效果（在博客内）