问题描述
Czy喜欢将他的妹子们排成一队。假设他拥有N只妹纸，编号为1至N。Czy让他们站成一行，等待自己来派送营养餐。这些妹纸按照编号大小排列，并且由于它们都很想早点吃饭，于是就很可能出现多只妹纸挤在同一位置的情况(也就是说，如果我们认为妹纸位于数轴上，那么多只妹纸的位置坐标可能相同)。
因为众所周知的原因，某些妹纸之间互相喜欢，他们希望互相之间的距离至多为一个定值。但某些妹纸之间互相厌恶，他们希望互相之间的距离至少为一个定值。现在给定ML个互相喜爱的妹纸对以及他们之间距离的最大值，MD个互相厌恶的妹纸对以及他们之间距离的最小值。
你的任务是计算在满足以上条件的前提下，帮助Czy计算出编号为1和编号为N的妹纸之间距离的最大可能值。
输入
输入文件为 layout.in。
第一行有 3 个整数，每两个整数之间用一个空格隔开，依次表示 n,ML和DL ；
此后ML行，每行包含三个用空格分开的整数A,B和D，其中A,B满足1<=A<=B<=N。表示编号为A和B的妹纸之间的距离至多为D。
此后MD行，每行包含三个用空格分开的整数A,B和D，其中A,B满足1<=A<=B<=N。表示编号为A和B的妹纸之间的距离至少为D。
输出
输出文件名为 layout.out。
输出文件仅包含一个整数。如果不存在任何合法的排队方式，就输出-1。如果编号1和编号N的妹纸间距离可以任意，就输出-2 。否则输出他们之间的最大可能距离。
样例输入输出
layout.in
4 2 1
2 4 20
2 3 3
1 3 10
layout.out
27
数据范围
对于40%的数据，N<=100；
对于100%的数据，N<=1000；ML,MN<=10000；D<=1000000。
题解
差分约束。考了才发现自己之前的理解一点都不透彻。形如A+d>=B的约束条件，要求我们在图论上求“最短”路，因为要求A+d>=B，所以对于所有A+d<B的情况，B都应被更新。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1e15
using namespace std;
int n,ml,md,tag;
int zz,head[1002];
struct bian{int to,nx; ll v;} e[200002];
int pd[1002],q[1002];
ll dis[1002];
void insert(int x,int y,ll z)
{zz++; e[zz].to=y; e[zz].v=z; e[zz].nx=head[x]; head[x]=zz;}
void init()
{
scanf("%d%d%d",&n,&ml,&md);
int i,x,y;
ll z;
for(i=1;i<=ml;i++)
{scanf("%d%d%I64d",&x,&y,&z);
insert(x,y,z);
}
for(i=1;i<=md;i++)
{scanf("%d%d%I64d",&x,&y,&z);
insert(y,x,-z);
}
}
void dfs(int x)
{
pd[x]=1;
int i,p;
for(i=head[x];i;i=e[i].nx)
{if(tag==-1) return;
p=e[i].to;
if(dis[p]>dis[x]+e[i].v)
{if(pd[p]) {tag=-1; return;}
dis[p]=dis[x]+e[i].v;
dfs(p);
}
}
pd[x]=0;//这点一定要有。
}
void work()
{
int i;
for(i=1;i<=n;i++) dis[i]=inf;
dis[1]=0;
dfs(1);
if(tag==-1) {printf("-1\n"); return ;}
for(i=1;i<=n;i++) {dis[i]=inf; pd[i]=0;}
dis[1]=0; q[0]=1; pd[1]=1;
int t=0,w=1,x,p;
while(t!=w)
{x=q[t]; t=(t+1)%n;
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
if(dis[p]>dis[x]+e[i].v)
{dis[p]=dis[x]+e[i].v;
if(!pd[p])
{pd[p]=1; q[w]=p; w=(w+1)%n;}
}
}
pd[x]=0;
}
if(dis[n]==inf) printf("-2\n");
else printf("%I64d\n",dis[n]);
}
int main()
{
freopen("layout.in","r",stdin);
freopen("layout.out","w",stdout);
init(); work();
return 0;
}