题意：
有一排按顺序排列的牛，i在i+1的前面。
牛之间存在2种关系：(i < j)
(i,j,a):i希望离j的距离不超过a；
(i,j,b):i希望离j的距离不小于b；
有可能许多牛是在同一个位置。
给出一些关系，求第一头牛和最后一头牛的距离的最大值。
思路：
通过两个关系可以得出两个不等式
1：d[i] + a >= d[j]
2：d[i] + a <= d[j]
有若干个形如上式的不等式，称为差分约束系统，采用最短路的方式求解。
首先把不等式转化为统一的大于等于的形式（大于等于对应于最短路，小于等于对应于最长路）。
之后，对应于统一的d[i] + a >= d[j]的形式，则添加一条从i到j的权值为a的边；
题中还有隐藏关系d[i] <= d[i+1] + 0，则添加一条从i+1到i的权值为0的边。
因为有负权边，所以用bellman-ford算法。
当第n次还有边更新的时候，说明有负权回路，无解。其他情况有解。
坑：
poj 强行 while (scanf())。。。
代码：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 struct edge{ int from,to,cost; }; 8 9 edge es[30005];10 11 int dis[1005];12 13 const int inf = 0x3f3f3f3f;14 15 bool spfa(int n,int en)16 {17 memset(dis,inf,sizeof(dis));18 19 dis[1] = 0;20 21 for (int i = 1;i <= n;i++)22 {23 for (int j = 0;j < en;j++)24 {25 edge e = es[j];26 27 if (dis[e.to] > dis[e.from] + e.cost)28 {29 dis[e.to] = dis[e.from] + e.cost;30 31 if (i == n) return true;32 }33 }34 }35 36 return false;37 }38 39 int main()40 {41 int n,ml,md;42 43 while (scanf("%d%d%d",&n,&ml,&md) != EOF)44 {45 int cnt = 0;46 47 for (int i = 1;i < n;i++)48 {49 es[cnt].from = i + 1;50 es[cnt].to = i;51 es[cnt].cost = 0;52 cnt++;53 }54 55 for (int i = 0;i < ml;i++)56 {57 int a,b,d;58 59 scanf("%d%d%d",&a,&b,&d);60 61 es[cnt].from = a;62 es[cnt].to = b;63 es[cnt].cost = d;64 65 cnt++;66 }67 68 for (int i = 0;i < md;i++)69 {70 int a,b,d;71 72 scanf("%d%d%d",&a,&b,&d);73 74 es[cnt].from = b;75 es[cnt].to = a;76 es[cnt].cost = -d;77 78 cnt++;79 }80 81 bool f = spfa(n,cnt);82 83 if (f) printf("-1\n");84 else if (dis[n] == inf) printf("-2\n");85 else printf("%d\n",dis[n]);86 }87 88 return 0;89 }