Description
Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.
Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.
Input
Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.
Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.
Output
Sample Input
4 2 1
1 3 10
2 4 20
2 3 3
Sample Output
27
There are 4 cows. Cows #1 and #3 must be no more than 10 units apart, cows #2 and #4 must be no more than 20 units apart, and cows #2 and #3 dislike each other and must be no fewer than 3 units apart.
The best layout, in terms of coordinates on a number line, is to put cow #1 at 0, cow #2 at 7, cow #3 at 10, and cow #4 at 27.
Source
正解：差分约束系统+SPFA
解题报告：
大概题意是给定排成一列的牛，然后两头牛之间的距离可能要大于等于某个值或者小于等于某个值，问是否存在或者终点是否可以无限远。
以前在codevs上面做过一道差分约束系统的题，然后就学会了这种神奇的思想。其实思想很简单，结合图论的话还是很有用的。
考虑题意，需要求1到n的最大距离。题目中给了很多限制条件，比如说x2-x1<=3,x4-x2>=6这样的条件。我们考虑像x2-x1<=3这样的条件，因为我们想让距离尽可能大，就要使距离最大化，然后建图，1向2连一条权值为3的边。那么像x4-x2>=6这样大于的怎么办呢，我们就可以把它变成x2-x4<=-6，边权为负即可。然后图上跑SPFA。
接着是个很重要的问题，是最短路还是最长路呢？按理说要想距离大应该跑最长路，但是我们想，我们这个图是怎么建的，根据每个条件的最大条件连边，那么说明我们肯定要取所有对这个点的约束中最小的那个（取交），所以只会越来越小。不难想到，最后求出的dis[n]就是我们要求的。
题意中的-1、-2怎么特判呢？如果有负权环就说明不可能，记一下每个点入队n次就说明有负权环。而可以无限大则说明还到不了n，则说明dis[n]仍为初值
轻松AC，代码如下：
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#ifdef WIN32
#define OT "%I64d"
#else
#define OT "%lld"
#endif
using namespace std;
typedef long long LL;
const int MAXN = ;
const int MAXM = ;
const int inf = (<<);
int n,m1,m2;
int first[MAXN],to[MAXM],next[MAXM],w[MAXM],ecnt;
int dis[MAXN];
queue<int>Q;
bool pd[MAXN];
int cnt[MAXN]; inline int getint()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} inline void link(int x,int y,int z){
next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; w[ecnt]=z;
} inline bool spfa(){
Q.push(); pd[]=;
for(int i=;i<=n;i++) dis[i]=inf;
while(!Q.empty()){
int u=Q.front(); Q.pop(); pd[u]=;
for(int i=first[u];i;i=next[i]) {
int v=to[i];
if(dis[v]>dis[u]+w[i]) {
dis[v]=dis[u]+w[i];
if(!pd[v]) {
Q.push(v);
pd[v]=;
cnt[v]++;
if(cnt[v]>=n) return false;
}
}
}
}
if(dis[n]==inf) printf("-2");
else printf("%d",dis[n]);
return true;
} inline void solve(){
n=getint(); m1=getint(); m2=getint();
int x,y,z;
for(int i=;i<=m1;i++) {
x=getint();y=getint();z=getint();
link(x,y,z);
}
for(int i=;i<=m2;i++) {
x=getint(); y=getint(); z=getint();
link(y,x,-z);
}
if(!spfa()) printf("-1");
} int main()
{
solve();
return ;
}