BZOJ 1731 [Usaco2005 dec]Layout 排队布局

题目大意

给你一堆牛，它们站在数轴上，可能重合，还有一堆关系，形如(X,Y,Z)表示X和Y的距离不小于/不大于Z。问N号牛最远位置。

差分约束系统，直接根据$dis_y \leq dis_x+val_i$的定理建图跑最短路即可。

注意差分约束系统想跑啥跑啥不是必须最长路/最短路！只要建图方式和跑法匹配就可以……

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,ml,md,inx,iny,inz,dis[1010];
int to[40010],nex[40010],val[40010],head[1010],tot,cnt[1010];
bool inq[1010];
queue<int>q;
void addedge(int tx,int ty,int tz) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;}
bool spfa()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    inq[1]=true;
    cnt[1]=1;
    q.push(1);
    while(!q.empty())
    {
        int tmp=q.front();
        q.pop();
        inq[tmp]=false;
        for(int i=head[tmp];i;i=nex[i])
            if(dis[to[i]]>dis[tmp]+val[i])
            {
                dis[to[i]]=dis[tmp]+val[i];
                if(!inq[to[i]])
                {
                    inq[to[i]]=true;
                    cnt[to[i]]++;
                    if(cnt[to[i]]>=n) return false;
                    //printf("%d %d %d\n",tmp,to[i],dis[to[i]]);
                    q.push(to[i]);
                }
            }
    }
    return true;
}
int main()
{
	scanf("%d%d%d",&n,&ml,&md);
	for(int i=1;i<=n;++i) addedge(i+1,i,0);
	for(int i=1;i<=ml;++i) scanf("%d%d%d",&inx,&iny,&inz),addedge(inx,iny,inz);
	for(int i=1;i<=md;++i) scanf("%d%d%d",&inx,&iny,&inz),addedge(iny,inx,-inz);
	if(!spfa()) dis[n]=-1;
	if(dis[n]==0x3f3f3f3f) dis[n]=-2;
	printf("%d\n",dis[n]);
	return 0;
}