RT, 菜鸡写的和第一篇题解差不多 不过加边和SPFA的板子大概是我自己写的呢qwq

只得了28pts 有RE也有WA ◔ ‸◔？

( ╯#-_-)╯┴—┴掀桌

自己调了快一天了也没检查出来qwq 求神仙们帮忙看看 本萌新感激不尽呢ヽ(｡◕‿◕｡)ﾉﾟ

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
#define maxn 2003
#define maxm 6006

using namespace std;

int t, n, m, u, v, w;
int dis[maxn];
bool vis[maxn];
struct edge{
	int v, w, next;
}e[maxm];
int h[maxn], tot; 
int in[maxn];

void add_edge(int u1, int v1, int w1){
	e[++tot].next = h[u1];
	h[u1] = tot;
	e[tot].v = v1;
	e[tot].w = w1;
}

bool SPFA(){
	queue<int> q; 
	q.push(1); vis[1] = true; in[1]++; dis[1] = 0;
	while(q.size()){
		int p = q.front();
		vis[p] = false;
		q.pop();
		for(register int i = h[p]; i; i = e[i].next){
			int vv = e[i].v;
			if(dis[vv] > e[i].w + dis[p]){
				in[vv]++;
				dis[vv] = e[i].w + dis[p];
				if(in[vv] >= n) return true;
				if(!vis[vv]){
					vis[vv] = true;
					q.push(vv);
				}
			}
		}
	}
	return false;
} 
int main(){
	cin>>t;
	for(int k = 1; k <= t; k++){
		memset(h, 0, sizeof(h));
		memset(in, 0, sizeof(in));
		memset(vis, false, sizeof(vis));
		memset(dis, 0x3f, sizeof(dis));
		memset(e, 0, sizeof(e));
		cin>>n>>m;	
		tot = 0; 
		for(int j = 1; j <= m; j++){
			cin>>u>>v>>w;
			if(w >= 0) {
				add_edge(u, v, w);
				add_edge(v, u, w);
			}
			else add_edge(u, v, w);
		}
	
		if(SPFA()) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}