约束差分

http://poj.org/problem?id=3169
对于任意i号奶牛，1<=i<N，在距离上应该满足：
D[i+1] - D[i] >= 0
对于每个好感的描述(i，j，k)，假设i<=j，体现到距离上的要求就是：
D[j] - D[i] <= k
对于每个反感的描述(i，j，k)，假设i<=j，体现到距离上的要求就是：
D[j] - D[i] >= k

写成我们约定的形式：
D[j] -D[i ]<= k
D[i] - D[j] <= - k
.对于差分不等式，a - b <= c ，建一条 b 到 a 的权值为 c 的边，求的是最短路，得到的是最大值（本题求的就是最大值），对于不等式 a - b >= c ，建一条 b 到 a 的权值为 c 的边，求的是最长路，得到的是最小值。

#include<cstdio>
#include<string.h>
using namespace std;
struct Node
{
    int from,to,w;

}edge[20010];
int n,m,k,dis[1010],INF=0x3f3f3f3f;
void init()
{
    memset(dis,INF,sizeof(dis));
    dis[1]=0;
}
bool Bellman_Ford()
{
    int sum=m+k;
    bool flag;
    for(int i=1;i<=n-1;i++)
    {
        flag=true;
        for(int j=0;j<sum;j++)
        {
            int u=edge[j].from,v=edge[j].to,val=edge[j].w;
            if(dis[v]>dis[u]+val)
            {
                dis[v]=dis[u]+val;
                flag=false;
            }
        }
        if(flag) break;
    }
   for(int j=0;j<sum;j++)
   {
        int u=edge[j].from,v=edge[j].to,val=edge[j].w;
            if(dis[v]>dis[u]+val)
            {
                return true;
            }
   }
   return false;
}
void reChange(int &a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}
int main()
{
    int u,v,val,t;
     scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            if(u>v) reChange(u,v);
            edge[i].from=u;
            edge[i].to=v;
            edge[i].w=val;
        }
        for(int i=m;i<m+k;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            if(u<v) reChange(u,v);
            edge[i].from=u;
            edge[i].to=v;
            edge[i].w=-val;
        }
        init();
        if(Bellman_Ford()) printf("-1\n");
        else if(dis[n]==INF) printf("-2\n");
        else printf("%d\n",dis[n]);
        //printf("%d\n",INF);
}