20pts求调

#include <bits/stdc++.h>
#define ll long long
#define N INT_MAX

using namespace std;

const ll M = pow(20, 5) + 10;
int T, n, m, u, v, w, cnt;
int dis[M], vis[M], head[M], p[M];

struct Edge
{
	int to;
	int w;
	int Next;
} edge[M];

void add(int u, int v, int w)
{
	edge[++cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].Next = head[u];
	head[u] = cnt;
}

void clean()
{
	cnt = 0;

	for (int i = 1; i <= n; i++)
	{
		dis[i] = N;
		vis[i] = head[i] = p[i] = 0;
	}
}

void spfa()
{
	queue <int> q;

	while (!q.empty())
		q.pop();

	q.push(1);
	vis[1] = 1;
	dis[1] = 0;

	while (q.empty() == false)
	{
		int t = q.front();
		q.pop();
		vis[t] = p[t] = 0;

		for (int i = head[t]; i != 0; i = edge[i].Next)
		{
			int k = edge[i].to;

			if (dis[k] > dis[t] + edge[i].w)
			{
				dis[k] = dis[t] + edge[i].w;


				if (vis[k] == 0)
				{

					p[k]++;

					if (p[k] >= n)
					{
						cout << "YES" << endl;
						return;
					}

					q.push(k);
					vis[k] = 1;
				}
			}
		}

	}

	cout << "NO" << endl;
	return;
}

int main()
{
	cin >> T;

	while (T--)
	{
		cin >> n >> m;

		for (int i = 1; i <= m; i++)
		{
			cin >> u >> v >> w;

			if (w >= 0)
			{
				add(u, v, w);
				add(v, u, w);
			}
			else
				add(u, v, w);
		}

		clean();
		spfa();
		clean();
	}

	system("pause");
	return 0;
}