poj-3259——bellmanford

题意很明显：判断是否有负权回路。
bellman_ford的算法实现过程：
首先明确一点 迄今 还不知道 判断完是否有负权后 怎么计算最短路。——有负权 没有最短路。无负权，dis中的最小距离即是所解
判断负权的过程：定义一个一维数组，存放的是每个点的最小距离(到源点的最小距离)（每次更新与其相连的两个点，最终存放的是该点在整个图中的最小距离），更新每个点的最小距离，如果某个点能更新n次说明存在负权。但是如果在某次缩边的过程中，没有可以缩边的点，也即说明已经找到最短距离，则不用缩边了，一定没有负权。
算法成立的原理：如果两点之间存在最短距离，则长度最大为n-1，如果，某个点经过了n次，说明存在负权。

#include<iostream>
using namespace std;
struct info
{
 int s,e,w;
}map[5500];
int dis[505];
int N,M,W,len;
bool bellman_ford()
{
 int i,j,k;int flag=1;
 for (i=0;i<N-1;i++)
 {
  for (j=0;j<len;j++)
  {
   if (dis[map[j].s]>dis[map[j].e]+map[j].w)
   {
    dis[map[j].s]=dis[map[j].e]+map[j].w;
    flag=2;
   }
  }
  if (flag==1)
  {
   break;
  }
 }
 for (j=0;j<len;j++)
 {
  if (dis[map[j].s]>dis[map[j].e]+map[j].w)
  {
   return true;
  }
 }
 return false;
}
int main()
{
 int n;
 cin>>n;
 while (n--)
 {
  int i,s,e,t;len=0;
  cin>>N>>M>>W;
  for (i=0;i<M;i++)
  {
   cin>>s>>e>>t;
   map[len].s=s;
   map[len].e=e;
   map[len++].w=t;
   map[len].s=e;
   map[len].e=s;
   map[len++].w=t;
  }
  for (i=0;i<W;i++)
  {
   cin>>s>>e>>t;
   map[len].s=s;
   map[len].e=e;
   map[len++].w=-t;
  }
  if (bellman_ford())
  {
   cout<<"YES"<<endl;
  }
  else cout<<"NO"<<endl;
 }
 return 0;
}