147
poj 3259 Wormholes 最短路
bellman判環即可
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
Build Time:2013-05-07-22.01
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int n,m,w;
int first[505];
int U[7000];
int next[7000];
int edge[7000];
int cnt;
void build(int v,int u,int s)
{
next[cnt]=first[v];
first[v]=cnt;
edge[cnt]=s;
U[cnt]=u;
cnt++;
}
queue<int> q;
int dis[505];
int in[505];
int bellman()
{
bool inq[505];
memset(inq,0,sizeof(inq));
memset(dis,127,sizeof(dis));
memset(in,0,sizeof(in));
while(!q.empty())q.pop();
q.push(1);
in[1]=1;
dis[1]=0;
int v,u,i,t;
while(!q.empty())
{
v=q.front();q.pop();
inq[v]=0;
for(i=first[v];i!=-1;i=next[i])
{
u=U[i];
if(dis[u]>(t=dis[v]+edge[i]))
{
dis[u]=t;
if(inq[u])continue;
inq[u]=1;
in[u]++;
if(in[u]>n)return 1;
q.push(u);
}
}
}
return 0;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(first,-1,sizeof(first));
cnt=0;
scanf("%d%d%d",&n,&m,&w);
int i,u,v,s;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&v,&u,&s);
build(v,u,s);
build(u,v,s);
}
for(i=0;i<w;i++)
{
scanf("%d%d%d",&v,&u,&s);
build(v,u,-s);
}
if(bellman())puts("YES");
else puts("NO");
}
}
最後更新：2017-04-03 18:51:50