测评结果

#include <bits/stdc++.h>
using namespace std;

int n , m , nxt[500100] , vxt[500100] , h[101000] , w[500100] , idx , cnt[101000];
long long dis[101000];
bool vis[10100];
queue <int> q;
void add_edge ( int u , int v , int wt )
{
	nxt[++ idx] = h[u];
	vxt[idx] = v;
	w[idx] = wt;
	h[u] = idx;
}
int main ()
{
	int t;
	cin >> t;
	while ( t -- )
	{
		memset ( h , - 1 , sizeof ( h ) );
		memset ( cnt , 0 , sizeof ( cnt ) );
		memset ( nxt , 0 , sizeof ( nxt ) );
		memset ( vxt , 0 , sizeof ( vxt ) );
		memset ( dis , 0x3f , sizeof ( dis ) );
		memset ( w , 0 , sizeof ( w ) );
		memset ( vis , false , sizeof ( vis ) );
		idx = 0;
		cin >> n >> m;
		for ( int i = 1 ; i <= m ; i ++ )
		{
			int u , v , w;
			scanf ( "%d %d %d" , & u , & v , & w );
			add_edge ( u , v , w );
			if ( w >= 0 )
			{
				add_edge ( v , u , w );
			}
		}
		while ( ! q.empty () )
		{
			q.pop ();
		}
		int wt;
		q.push ( 1 );
		cnt[1] = 1;
		dis[1] = 0;
		bool f = true;
		while ( ! q.empty () )
		{
			wt = q.front ();
			q.pop ();
			vis[wt] = false;
			for ( int i = h[wt] ; ~ i ; i = nxt[i] )
			{
				if ( dis[wt] + w[i] < dis[vxt[i]] )
				{
					dis[vxt[i]] = dis[wt] + w[i];
					cnt[vxt[i]] = cnt[wt] + 1;
					if ( cnt[vxt[i]] >= n )
					{
						cout << "YES\n";
						f = false;
						break;
					}
					if ( ! vis[vxt[i]] )
					{
						q.push ( vxt[i] );
						vis[vxt[i]] = true;
					}
				}
			}
			if ( ! f )
			{
				break;
			}
		}
		if ( f )
		{
			cout << "NO\n";
		}
	}
	return 0;
}