hdu3592(差分约束) （线性）

题意：一些牛按序号排成一条直线，有两种要求，A和B距离不得超过X，还有一种是A和B距离不得少于Y，问1和N可能的最大距离。

和poj那题一样，就是多了多组数据。

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<queue>

 #define INF 2000000007

 #define N 1007

 #define M 10007

 using namespace std;

 int n,l,r;

 int dis[N],num[N],ins[N];

 int cnt,head[N],Next[M*],rea[M*],val[M*];

 void add(int u,int v,int fee)

 {

     Next[++cnt]=head[u];

     head[u]=cnt;

     rea[cnt]=v;

     val[cnt]=fee;

 }

 bool Spfa()

 {

     for (int i=;i<=n;i++)

         ins[i]=,dis[i]=INF,num[i]=;

     queue<int>q;

     q.push();dis[]=,num[]=;

     while(!q.empty())

     {

         int u=q.front();q.pop();

         for (int i=head[u];i!=-;i=Next[i])

         {

             int v=rea[i],fee=val[i];

             if (dis[v]>dis[u]+fee)

             {

                 dis[v]=dis[u]+fee;

                 if (!ins[v])

                 {

                     num[v]++;

                     ins[v]=;

                     q.push(v);

                     if (num[v]>n) return false;

                 }

             }

         }

         ins[u]=;

     }

     return true;

 }

 int main()

 {

     int T;scanf("%d",&T);

     while(T--)

     {

         cnt=;

         memset(head,-,sizeof(head));

         scanf("%d%d%d",&n,&l,&r);

         for (int i=,x,y,z;i<=l;i++)

         {

             scanf("%d%d%d",&x,&y,&z);

             add(x,y,z);

         }

         for (int i=,x,y,z;i<=r;i++)

         {

             scanf("%d%d%d",&x,&y,&z);

             add(y,x,-z);

         }

         for (int i=;i<=n;i++)

             add(i+,i,);

         bool flag=Spfa();

         if (!flag) printf("-1\n");

         else

         {

             if (dis[n]==INF) printf("-2\n");

             else printf("%d\n",dis[n]);

         }

     }

 }