萌新求助11分

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

const int N=3010;
int n,m,start;
int to[N],nxt[N],h[N],tot,w[N];
int dis[N],inq[N],cnt[N],V[N];

void add(int x,int y,int z)
{
	to[++tot]=y;
	nxt[tot]=h[x];
	h[x]=tot;
	w[tot]=z;
}

bool SPFA()
{
	queue<int> q;
	q.push(0);
	dis[0]=0;
	inq[0]=1;
	while(q.size())
	{
		int x=q.front();
		if(cnt[x]>n)return false;
		q.pop();
		inq[x]=0;
		for(int i=h[x];i;i=nxt[i])
		{
			int y=to[i],z=w[i];
			if(dis[y]>dis[x]+z)
			{
				dis[y]=dis[x]+z;
				cnt[y]++;
				if(!inq[y])q.push(y),inq[y]=1;
			}
		}
	}
	return true;
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(h,0,sizeof h);
		memset(cnt,0,sizeof cnt);
		memset(dis,0x3f,sizeof dis);
		memset(V,0,sizeof V);
		tot=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			y+=1;
			add(x,y,-z);
			add(y,x,z);
			V[x]=V[y]=1;
		}
		for(int i=1;i<=n+1;i++)if(V[i])add(0,i,0);
		if(SPFA())cout<<"true\n";
		else cout<<"false\n";
	}
	return 0;
}