<题目链接>
题目大意：
一些母牛按序号排成一条直线。有两种要求，A和B距离不得超过X，还有一种是C和D距离不得少于Y，问可能的最大距离。如果没有最大距离输出-1，如果1、n之间距离任意就输出-2，否则输出最大的距离。
解题分析：
典型的差分约束，第一种约束，v-u<=c；第二种约束：v-u>=c 可以转化为 u-v<=c ，还有一种约束，因为题目要求按序号排序，所以 loc[i] - loc[i-1]>=0 ，即 loc[i-1]-loc[i]<=0 。以上就是本题的三种约束，利用上述三种约束建图，然后跑一遍最短路即可，因为可能存在负权边，所以用spfa求解。当该图存在负环的时候输出-1，当1~n不连通的时候输出-2，否则输出1---->n的最短边权约束和。即所求的最大距离。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std; const int N =1e3+;
const int M =2e5+;
#define INF 0x3f3f3f3f
struct EDGE{
int to,val,next;
}edge[M];
int head[N],dis[N],cnt[N],tot,n,ml,md;
bool vis[N]; void init(){
memset(head,-,sizeof(head));
tot=;
}
void add(int u,int v,int w){
edge[++tot].to=v,edge[tot].val=w;
edge[tot].next=head[u],head[u]=tot;
}
int spfa(int s){ //因为存在负权边，所以用spfa求最短路
memset(dis,INF,sizeof(dis));
memset(vis,false,sizeof(vis));
memset(cnt,,sizeof(cnt));
queue<int>q;
q.push(s);
vis[s]=true,cnt[s]=,dis[s]=;
while(!q.empty()){
int cur=q.front();
q.pop();
vis[cur]=false;
for(int i=head[cur];~i;i=edge[i].next){
int v=edge[i].to;
if(dis[v]>dis[cur]+edge[i].val){
dis[v]=dis[cur]+edge[i].val;
if(!vis[v]){
vis[v]=true;
if(++cnt[v]>n)return -; //进队列次数>n，说明存在负环，直接返回-1
q.push(v);
}
}
}
}
if(dis[n]==INF)return -; //如果两点不连通，说明1、n两点之间没有约束条件，所以1、n可以距离任意远，返回-2
return dis[n];
}
int main(){
while(scanf("%d%d%d",&n,&ml,&md)!=EOF){
init();
for(int i=;i<=n;i++)add(i,i-,); //代表s[i-1]-s[i]<=0
for(int i=;i<=ml;i++){
int u,v,c;scanf("%d%d%d",&u,&v,&c);
add(u,v,c); //v-u<=c
}
for(int i=;i<=md;i++){
int u,v,c;scanf("%d%d%d",&u,&v,&c);
add(v,u,-c); //u-v<=-c,即v-u>=c
}
//利用题目条件，整合成三个差分约束条件，利用这几个条件建图，然后跑一遍最短路
printf("%d\n",spfa());
}
}
2018-10-11