题目链接http://poj.org/problem?id=3169
题目大意：
一些牛按序号排成一条直线。
有两种要求，A和B距离不得超过X，还有一种是C和D距离不得少于Y，问可能的最大距离。如果没有输出-1，如果可以随便排输出-2，否则输出最大的距离。
首先关于差分约束：https://blog.csdn.net/consciousman/article/details/53812818
了解了差分约束之后就知道该题典型的差分约束+spfa即可。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
struct pot{
int to;
int next;
int len;
}edge[];
int next[];
int d[];
int cnt[];
bool vis[];
int que[];
int tot=,front=,back=;
int n,m,q;
void add(int x,int y,int t)
{
edge[tot].to=y;
edge[tot].len=t;
edge[tot].next=next[x];
next[x]=tot++;
}
bool spfa()
{
d[]=;
vis[]=true;
que[front++]=;
cnt[]++;
while(front!=back)
{
back++;
if(back>=)back=;
vis[que[back]]=false;
for(int i = next[que[back]];i!=-;i=edge[i].next)
{
if(d[edge[i].to]>d[que[back]]+edge[i].len)
{
d[edge[i].to]=d[que[back]]+edge[i].len;
if(!vis[edge[i].to])
{
que[front++]=edge[i].to;
if(front>=)front=;
vis[edge[i].to]=true;
cnt[edge[i].to]++;
if(cnt[edge[i].to]>n)return false;
}
}
}
}
return true;
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i = ;i <= n ; i++)
{
next[i]=-;
d[i]=INF;
vis[i]=false;
cnt[i]=;
}
for(int i = ; i < m ; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a>b)
{
int t=a;
a=b;
b=t;
}
add(a,b,c);
}
for(int i = ; i < q ; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(b>a)
{
int t=a;
a=b;
b=t;
}
add(a,b,-c);
}
if(!spfa())printf("-1\n");
else if(d[n]==INF)printf("-2\n");
else printf("%d\n",d[n]);
return ;
}