今天来回顾了一下负环，一开始代码是这样的：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <queue>

using namespace std;

struct edge {
	int next, to, w;
};

int t, n, m, x, y, w, cur, cnt[2005], dis[2005], head[2005];
queue<int> q;
edge e[6005];

inline int read() {
	char ch = getchar();
	int num = 0, flag = 1;
	while (!isdigit(ch)) {
		if (ch == '-')
			flag *= -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return num * flag;
}

inline void add(int u, int v, int w) {
	++cur;
	e[cur] = {head[u], v, w};
	head[u] = cur;
}

inline bool spfa(int s) {
	memset(dis, 0x3f, sizeof(dis));
	memset(cnt, 0, sizeof(cnt));
	dis[s] = 0;
	cnt[s] = 1;
	q.push(s);
	while (!q.empty()) {
		x = q.front();
		q.pop();
		for (register int i = head[x]; i; i = e[i].next)
			if (dis[x] + e[i].w < dis[e[i].to]) {
				dis[e[i].to] = dis[x] + e[i].w;
				q.push(e[i].to);
				cnt[e[i].to] = cnt[x] + 1;
				if (cnt[e[i].to] > n)
					return true;
			}
	}
	return false;
}

int main() {
	t = read();
	while (t--) {
		n = read();
		m = read();
		memset(head, 0, sizeof(head));
		memset(e, 0, sizeof(edge));
		cur = 0;
		while (m--) {
			x = read();
			y = read();
			w = read();
			add(x, y, w);
			if (w >= 0)
				add(y, x, w);
		}
		if (spfa(1))
			printf("YES");
		else
			printf("NO");
		putchar('\n');
	}
	return 0;
}

可以很容易发现队列 $q$ 多测没清空，但是它 AC 了（（

然后我加上清空 $q$：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <queue>

using namespace std;

struct edge {
	int next, to, w;
};

int t, n, m, x, y, w, cur, cnt[2005], dis[2005], head[2005];
queue<int> q;
edge e[6005];

inline int read() {
	char ch = getchar();
	int num = 0, flag = 1;
	while (!isdigit(ch)) {
		if (ch == '-')
			flag *= -1;
		ch = getchar();
	}
	while (isdigit(ch) {
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return num * flag;
}

inline void add(int u, int v, int w) {
	++cur;
	e[cur] = {head[u], v, w};
	head[u] = cur;
}

inline bool spfa(int s) {
	memset(dis, 0x3f, sizeof(dis));
	memset(cnt, 0, sizeof(cnt));
	dis[s] = 0;
	cnt[s] = 1;
	while (!q.empty()) //added
		q.pop(); //added
	q.push(s);
	while (!q.empty()) {
		x = q.front();
		q.pop();
		for (register int i = head[x]; i; i = e[i].next)
			if (dis[x] + e[i].w < dis[e[i].to]) {
				dis[e[i].to] = dis[x] + e[i].w;
				q.push(e[i].to);
				cnt[e[i].to] = cnt[x] + 1;
				if (cnt[e[i].to] > n)
					return true;
			}
	}
	return false;
}

int main() {
	t = read();
	while (t--) {
		n = read();
		m = read();
		memset(head, 0, sizeof(head));
		memset(e, 0, sizeof(edge));
		cur = 0;
		while (m--) {
			x = read();
			y = read();
			w = read();
			add(x, y, w);
			if (w >= 0)
				add(y, x, w);
		}
		if (spfa(1))
			printf("YES");
		else
			printf("NO");
		putchar('\n');
	}
	return 0;
}

于是又 AC 了。

然后我就开始对拍这两个程序，得到了一组 hack，为了验证正确性，我又分别测了 iMya_nlgau 没清队列的代码和 Daniel_7216 清了队列（局部定义队列）的代码，前者挂掉后者正确。

hack 在 U412598 的附件中。

请求添加 hack 数据并撤下 iMya_nlgau、Push_Y、珈乐唯毒 的题解。