题意：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次，然后判断是否达到完全松弛，如果没，就说明存在负权。

题目思路：

我们发现，如果最大堆-次大堆<=1，那么问题肯定有解：我们可以从最大和次大里面每次拿一个，然后等他们和第三大堆相等的时候，每次从三堆里面各拿一个，等他们和第四大堆相等的时候，每次从四堆里面各拿一个，这样一直拿完所有堆。

问题变成了能不能使得最大堆-次大堆<=1，所以之前我们会从次大堆之外的那些堆里面取，来让最大堆减少，如果能减到：最大堆-次大堆<=1，那么原问题有解。

能否减到要看：

sum - max - max2 >= max - max2 - 1

是否成立，其中sum为总和，max为最大堆，max2为次大。

整理得：

2 * max - sum <= 1

应该这样就可以了。

源程序代码：

#include<stdio.h>
int main()
{
    long n,m,x,max;
    long sum;
    scanf("%d",&n);
    while(n--)
   {
        scanf("%d",&m);
        sum=0;
        max=0;
        while(m--)
         {
           scanf("%d",&x);
           sum+=x;
           if(max<x)
      max=x;
         }
   max<=sum-max+1?    
    printf("Yes\n"): printf("No\n");
    }
return 0;
}