poj 3259 ：Wormholes (bellman_ford)

题意：John的农场里field块地，path条路连接两块地，hole个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来，看到了离开之前的自己。

题目分析：这题存在负权所以Dijkstra在这里就不能用了，这个题目的本质就是判断负权是否存在，如果存在就可以满足题目要求。没有的话就不可能。

#include<iostream>

using namespace std;

const int inf=10000;

int num_count,edg;

struct {

      int star;

      int end;

      int time;

}sim[10000];

int dic[10000];

bool judge(){

      int flag;

      for(int i=2;i<=num_count;i++)

              dic[i]=inf;

     for(int i=1;i<=num_count;i++){

            flag=1;//加个判断是否完全松弛，优化算法，减少运行时间。

            for(int j=1;j<=edg;j++){  

                     int u=sim[j].star;

                     int v=sim[j].end;

                     int w=sim[j].time;

                     if(dic[v]>dic[u]+w){//松弛操作

                               flag=0;

                               dic[v]=dic[u]+w ;

                      }                          

            }

            if(flag)

                    break;

     }

            for(int j=1;j<=num_count;j++){//判断是否存在负权。

                     int u=sim[j].star;

                     int v=sim[j].end;

                     int w=sim[j].time;

                     if(dic[v]>dic[u]+w)

                               return false;

             }

             return true;

}

int main(){

      int cas,n,path,hole;

      cin>>cas;

      while(cas--){

             int a,b,c,k=0;

             scanf("%d%d%d",&n,&path,&hole);

             for(int i=1;i<=path;i++){

                      scanf("%d%d%d",&a,&b,&c);

                      k++;

                      sim[k].star=a;

                      sim[k].end=b;

                      sim[k].time=c;

                       k++;   

                      sim[k].star=b;

                      sim[k].end=a;

                      sim[k].time=c;

             }

            for(int i=1;i<=hole;i++){

                       scanf("%d%d%d",&a,&b,&c);

                       k++;

                       sim[k].star=a;

                       sim[k].end=b;

                       sim[k].time=-c;

           }

     num_count=n;

     edg=k;

     if(!judge())

             cout<<"YES"<<endl;

     else

             cout<<"NO"<<endl;

     }

    return 0;

}

题目总结：开始的时候用n,edg作为节点个数和边的个数，在主函数，和功能函数中都是用这个，发现即使把他们定义为全局变量都会出错，后来决定分别用四个变量来完成记录点数，边数。

这个题目的思路就是判断是否存在负权，只要进行松弛n次，然后判断是否达到完全松弛，如果没，就说明存在负权。