萌新用 SLF 优化后的 spfa 总是 WA on test9，但将双端队列改为普通队列后就 AC 了，为何？

原 SLF 优化代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <deque>
using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;

struct Edge {
	int u, v; ll w; int nxt;
} edge[maxn]; int head[maxn], tot;

inline void init(int u, int v, ll w) {
	edge[++tot] = (Edge){ u, v, w, head[u] }; head[u] = tot;
}

int T, n, m, in[maxn]; ll d[maxn]; bool inq[maxn];

bool spfa(int s) {
	deque<int> q;
	q.push_back(s); d[s] = 0; inq[s] = true; ++in[s];
	while (q.size()) {
		int u = q.front(); q.pop_front(); inq[u] = false;
		for (int i = head[u]; i; i = edge[i].nxt) {
			int v = edge[i].v; ll w = edge[i].w;
			if (d[u] + w < d[v]) {
				d[v] = d[u] + w;
				if (!inq[v]) {
					if (q.size() && d[v] < d[q.front()]) q.push_front(v);
					else q.push_back(v);
					++in[v]; inq[v] = true;
					if (in[v] > (n << 2)) return true;
				}
			}
		}
	}
	return false;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		memset(head, 0, sizeof(head)); memset(d, 0x3f, sizeof(d)); memset(in, 0, sizeof(in)); memset(inq, false, sizeof(inq)); tot = 0;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; ++i) {
			int p1, p2; ll pw; scanf("%d%d%lld", &p1, &p2, &pw);
			if (pw >= 0) init(p1, p2, pw), init(p2, p1, pw);	
			else init(p1, p2, pw);
		}
		if (spfa(1)) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

普通队列代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;

struct Edge {
	int u, v; ll w; int nxt;
} edge[maxn]; int head[maxn], tot;

inline void init(int u, int v, ll w) {
	edge[++tot] = (Edge){ u, v, w, head[u] }; head[u] = tot;
}

int T, n, m, in[maxn]; ll d[maxn]; bool inq[maxn];

bool spfa(int s) {
	queue<int> q;
	q.push(s); d[s] = 0; inq[s] = true; ++in[s];
	while (q.size()) {
		int u = q.front(); q.pop(); inq[u] = false;
		for (int i = head[u]; i; i = edge[i].nxt) {
			int v = edge[i].v; ll w = edge[i].w;
			if (d[u] + w < d[v]) {
				d[v] = d[u] + w;
				if (!inq[v]) {
					q.push(v);
					++in[v]; inq[v] = true;
					if (in[v] > n + 10) return true;
				}
			}
		}
	}
	return false;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		memset(head, 0, sizeof(head)); memset(d, 0x3f, sizeof(d)); memset(in, 0, sizeof(in)); memset(inq, false, sizeof(inq)); tot = 0;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; ++i) {
			int p1, p2; ll pw; scanf("%d%d%lld", &p1, &p2, &pw);
			if (pw >= 0) init(p1, p2, pw), init(p2, p1, pw);	
			else init(p1, p2, pw);
		}
		if (spfa(1)) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}