Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## SPFA 175ms

Posted by lzxzy at 2018-12-22 19:24:26 on Problem 3259
```#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF=10000000;
int n,m,knum,id;

struct edge
{
int v,w,nx;
}set[6005];
bool vis[505];
queue<int> Q;

{
}

void init()
{
int u,v,w;id=0;
scanf("%d%d%d",&n,&m,&knum);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
}
for(int i=1;i<=knum;i++)
{
scanf("%d%d%d",&u,&v,&w);
}
}

bool spfa()
{
memset(vis,0,sizeof(vis));
memset(Count,0,sizeof(Count));
for(int i=2;i<=n;i++)dis[i]=INF;
int u,v,tmp;Q.push(1);vis[1]=1;dis[1]=0;
while(!Q.empty())
{
u=Q.front();Q.pop();
{
v=set[k].v;
if(dis[u]+set[k].w<dis[v])
{
dis[v]=dis[u]+set[k].w;
if(!vis[v])
{
Q.push(v);Count[v]++;
if(Count[v]>=n)return false;
vis[v]=true;
}
}
}
vis[u]=false;
}
return true;
}

int main()
{
//	freopen("wormhole.in","r",stdin);
//	freopen("wormhole.out","w",stdout);
int cas;
scanf("%d",&cas);
while(cas--)
{
init();
if(spfa())puts("NO");
else puts("YES");
}
//	fclose(stdin); fclose(stdout);
return 0;
}```

Followed by: