如题，以下为加了SLF和LLL优化后代码

//SLF && LLL
#include<cstdio>
#include<cstring>
#include<deque>
#include<cmath>
#define N 2005
#define M 3005
#define INF 0x3f3f3f3f
int T, n, m, tot, num1, num2, cntp;
int h[N], cnt[N], dis[N];
bool vis[N];
struct node{
	int nxt, to, val;
}e[M << 1];
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch > '9' || ch < '0') (ch == '-') && (f = -1), ch = getchar();
	while(ch <= '9' && ch >= '0') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
}
void ae(int u, int v, int w){
	e[++tot].to = v;
	e[tot].nxt = h[u];
	e[tot].val = w;
	h[u] = tot;
	num1 += w;
}
std::deque<int>q;
void spfa(){
	std::memset(cnt, 0, sizeof(cnt));
	std::memset(vis, 0, sizeof(vis));
	std::fill(dis + 1, dis + n + 1, INF);
	while(!q.empty()) q.pop_front();
	int u = 1, v, w;
	dis[u] = 0, vis[u] = 1,cntp = 1, q.push_back(u);
	while(!q.empty()){
		u = q.front();
		while(dis[u] * cntp > num2){//LLL
			q.pop_front();
			q.push_back(u);
			u = q.front();
		}
		for(int i = h[u]; i; i = e[i].nxt){
			v = e[i].to; w = e[i].val;
			if(dis[u] + w < dis[v]){
				dis[v] = dis[u] + w;
				cnt[v] = cnt[u] + 1;
				if(cnt[v] >= n){
					printf("YES\n");
					return;
				}
				if(!vis[v]){
					vis[v] = 1;
					if(dis[v] > dis[u] + num1) q.push_back(v); //SLF with improvement
					else q.push_front(v);
				}
			}
		}
	}
	printf("NO\n");
}
int main(){
	T = read();
	while(T--){
		tot = 0, num1 = 0, num2 = 0, cntp = 0;
		n = read(), m = read();
		int u, v, w;
		std::memset(h, 0, sizeof(h));
		for(int i = 0; i < m; i++){
			u = read(), v = read(), w = read();
			ae(u, v, w);
			if(w >= 0) ae(v, u, w);
		}
		num1 = std::sqrt(num1);
		spfa();
	}
	return 0;
}