撰写
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
Hint
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
题意：这里又有一群牛站一排？？？然后一些牛不愿意和讨厌的人站的太近，而一些不愿意与它的朋友们离得太远（真实…）。问：最后一只牛与第一只牛最远的距离。
题解：差分约束，N大-N小>=d,N大-N小<=d,为了统一，将第二个条件转化为N小-N大>=-d，所以条件就是if(d[v]
代码：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(init,b,c) make_pair(init,make_pair(b,c))
#define rep(i,init,n) for (int i=init;i<=n;i++)
#define per(i,init,n) for (int i=n;i>=init;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll init, ll b) { return b ? gcd(b, init%b) : init; }
const int MAXN=1010;
const int INF=0x3f3f3f3f;
struct Edge
{
int v;
int l;
int cost;
Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,int w)
{
E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//在队列标志
int cnt[MAXN];//每个点的入队列次数
int dist[MAXN];
bool SPFA(int start,int n)
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
dist[i]=INF;
vis[start]=true;
dist[start]=0;
queue<int>que;
while(!que.empty())
que.pop();
que.push(start);
memset(cnt,0,sizeof(cnt));
cnt[start]=1;
while(!que.empty())
{
int t = que.front(); que.pop();
vis[t] = false;
for(int i = 0; i < E[t].size();i++){
int v = E[t][i].v;
int d = E[t][i].cost;
if(dist[v]>dist[t]+d){
dist[v] = dist[t]+d;
if(!vis[v]){
vis[v] = true;
que.push(v);
if(++cnt[v]>n) //cnt[i]为入队列次数，用来判定是否存在负环回路
return false;
}
}
}
}
return true;
}
int main(){
int n,ml,md;
scanf("%d%d%d", &n,&ml,&md);
while(ml--){
int u,v,d;
scanf("%d%d%d", &u,&v,&d);
addedge(u,v,d);
}
while(md--){
int u,v,d;
scanf("%d%d%d", &u,&v,&d);
addedge(v,u,-d);
}
if(!SPFA(1,n)) printf("-1\n");//无解
else if(dist[n]==INF) printf("-2\n");
else printf("%d\n",dist[n]);
return 0;
}