题目链接：http://poj.org/problem?id=3169
有n头牛站成一排 在他们之间有一些牛的关系比较好，所以彼此之间的距离不超过一定距离；也有一些关系不好的牛，希望彼此之间的距离大于等于一定距离；
关系好的有ml个（A B D）表示A牛和B牛之间的距离<=D 关系不好的有md个（A，B，D）表示A牛和B牛之间的距离>=D,求在满足条件的排列中，求出牛1和牛n的最大距离；
如果距离可以是无限大输出-2，如果不存在这样的排列输出-1；
我们用d[i]表示第i头牛的位置，因为牛是按照编号排列顺序的，
所以 d[i]-d[i-1]>=0； --------- d[i-1]-d[i]<=0;（i到i-1的距离是0）
关系好的 d[B]-d[A] <= C; --------- d[B]-d[A]<=C;（A到B的距离是C）
关系不好的 d[B]-d[a]>=C; ----------- d[A]-d[B]<=-C;（B到A的距离是-C）
我们要求是的d[n]-d[1]<=x中的x；
刚好满足差分约束系统，所以直接建图求1-n的最短路即可；如果存在负环则不存在这样的序列，用spfa判断负环，如果距离为无穷大说明可以是任意值，
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <string>
typedef long long LL;
#define INF 0x3f3f3f3f
#define met(a, b) memset(a, b, sizeof(a))
#define N 1500 using namespace std; int n, md, ml, G[N][N], vis[N], dist[N], cnt[N]; int spfa(int s)
{
for(int i=; i<=n; i++)
dist[i] = INF;
met(vis, );
met(cnt, );
queue<int>Q;
Q.push(s);
vis[s] = ;
dist[s] = ;
cnt[s]++;
while(!Q.empty())
{
int p = Q.front();Q.pop();
vis[p] = ;
cnt[p] ++;
for(int i=; i<=n; i++)
{
if(dist[i]>dist[p]+G[p][i])
{
dist[i] = dist[p]+G[p][i];
if(!vis[i])
{
vis[i] = ;
cnt[i]++;
if(cnt[i]>=n)
return -;
Q.push(i);
}
}
}
}
if(dist[n] == INF) return -;
return dist[n];
} int main()
{
while(scanf("%d %d %d", &n, &ml, &md) != EOF)
{
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
G[i][j] = INF;
G[i][i] = G[i][i-] = ;
}
int u, v, w;
for(int i=; i<=ml; i++)
{
scanf("%d %d %d", &u, &v, &w);
G[u][v] = w;
}
for(int i=; i<=md; i++)
{
scanf("%d %d %d", &u, &v, &w);
G[v][u] = -w;
} int ans = spfa();
printf("%d\n", ans);
}
return ;
}