题面:
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const int maxn=6100;
int head[maxn],ver[maxn],edge[maxn],nt[maxn];
int dis[maxn],sum[maxn],n,m,tot;
bool ha[maxn];
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z;
nt[tot]=head[x],head[x]=tot;
}
bool SPFA(int s)
{
memset(ha,0,sizeof(ha));
memset(sum,0,sizeof(sum));
memset(dis,0x3f,sizeof(dis));
queue<int>q;
q.push(s);
dis[s]=0;
ha[s]=true;
sum[s]++;
while(q.size())
{
int x=q.front();
q.pop();
ha[x]=false;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(dis[y]>dis[x]+z)
{
dis[y]=dis[x]+z;
if(!ha[y])
{
q.push(y);
ha[y]=true;
sum[y]++;
if(sum[y]>=n) return false;
}
}
}
}
return true;
}
int main(void)
{
int t;
int x,y,z;
scanf("%d",&t);
while(t--)
{
tot=0;
memset(head,0,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
if(z>=0) add(y,x,z);
}
if(SPFA(1)) printf("N0\n");
else printf("YE5\n");
}
return 0;
}