又是被黄题卡住的一天...
在强连通的诱惑下我毅然决然选择来讨论板白嫖求助,希望能有dalao发现
代码奉上
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define N 23333
#define inf 0x7fffffff
int t,n,m,num,head[N],dis[N],visn[N];
bool vis[N],jud;
struct Edge{
int to;
int next;
int val;
}edge[N];
void Addedge(int u,int v,int w)
{
edge[++num].to=v;
edge[num].next=head[u];
edge[num].val=w;
head[u]=num;
}
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
memset(head,0,sizeof(head));
memset(edge,0,sizeof(edge));
memset(vis,false,sizeof(vis));
memset(visn,0,sizeof(visn));
queue<int>q;
jud=false;
cin>>n>>m;
for(register int i=1;i<=n;i++)dis[i]=inf;
for(register int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
Addedge(x,y,z);
if(z>=0)Addedge(y,x,z);
}
dis[1]=0;q.push(1);vis[1]=true;visn[1]++;
while(!q.empty())
{
int fro=q.front();q.pop();vis[fro]=false;
for(register int i=head[fro];i;i=edge[i].next)
{
int to=edge[i].to;
if(dis[to]>dis[fro]+edge[i].val)
{
dis[to]=dis[fro]+edge[i].val;
visn[to]++;
if(visn[to]>=n){jud=true;break;}
if(!vis[to]){q.push(to);vis[to]=true;}
}
}
if(jud)break;
}
jud?cout<<"YES\n":cout<<"NO\n";
}
return 0;
}
太蒻了写SPFA果然容易炸(doogle