Bellman_Ford 算法，
利用Bellman_Ford算法判斷是否存在負回路。如果存在負回路就一定可以回到（不停的走這個回路，直到賺到的負值夠與回去的值抵消的），如果不存在一定不可以回去。
用cin500+ms， 用scanf 100+ms
#include<iostream>
#include<stdio.h>
using namespace std;
const int INF=0x0fffffff;
struct type
{
int s,t;
int len;
}edge[30000];
int n,m,w,nedge=0;
int d[505];
bool Bellman_Ford()
{
bool isPossible=false;
for(int j=1; j<=n; j++)d[j]=INF;
d[1]=0;
int u,v;
bool f;
for(int j=1; j<=n-1; j++)
{
f=0;
for(int k=1; k<=nedge; k++)
{
u=edge[k].s; v=edge[k].t;
if(d[v]>d[u]+edge[k].len)
d[v]=d[u]+edge[k].len;
f=1;
}
if(f==0)return false;
}
/*前面n-1次循環(huán)可以求出無負回路時的最短路徑，再來一次如果可以更新就一定有負回路。/*
for(int k=1; k<=nedge; k++)
{
u=edge[k].s; v=edge[k].t;
if(d[v]>d[u]+edge[k].len)
{ d[v]=d[u]+edge[k].len; return 1;}
}
// system("pause");
return 0;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int i,j,u,v,value;
scanf("%d %d %d",&n,&m,&w);//cin>>n>>m>>w;
nedge=0;
for(int i=1; i<=m; i++)
{
scanf("%d %d %d",&u,&v,&value);//cin>>u>>v>>value;
++nedge;
edge[nedge].s=u;
edge[nedge].t=v;
edge[nedge].len=value;
++nedge;
edge[nedge].s=v;
edge[nedge].t=u;
edge[nedge].len=value;
}
for(int i=1; i<=w; i++)
{
scanf("%d %d %d",&u,&v,&value);//cin>>u>>v>>value;
++nedge;
edge[nedge].s=u;
edge[nedge].t=v;
edge[nedge].len=-value;
/* ++nedge;
edge[nedge].s=v;
edge[nedge].t=u;
edge[nedge].len=-value;
*/
}
if(Bellman_Ford())
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
system("pause");
return 0;
}