小知识：差分约束的转化原理
差分约束系统的解法利用到了单源最短路径问题中的三角形不等式。即对于任何一条边u -> v，都有： d(v) <= d(u) + w(u, v) 题意：编号为1到n的牛排队有些牛是比较友好的需要使他们的相隔的最大距离不能大于某个值还有一些牛需要使他们的最小距离大于某个值求1号牛到n号牛之间能够相隔的最大距离 1、构造差分约束系统： A，B距离不超过D则B-A<=D， A,B距离至少为D则A-B<=-D. 2、若有解则求1和N之间的最短路径： 求最大距离符号需要小于等于，如果是符号是大于等于两边同时乘以-1 #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <queue> #include <math.h> using namespace std; const int inf=0x3f3f3f3f; const int maxn=2000; int n,ml,md; int head[maxn+10],cnt=0; struct node { int next,to,w; }edge[maxn*10+10]; void add(int u,int v,int w) { edge[cnt].to=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } bool vis[maxn]; int dis[maxn]; int du[maxn]; void spfa() { for(int i=1;i<=n;++i) { vis[i]=0; du[i]=0; dis[i]=inf; } vis[1]=1; dis[1]=0; du[1]=1; queue<int>que; que.push(1); while(!que.empty()) { int u=que.front(); que.pop(); vis[u]=0; for(int i=head[u];i!=-1; i=edge[i].next) { int v=edge[i].to,w=edge[i].w; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; if(!vis[v]) { du[v]++; vis[v]++; que.push(v); if(du[v]>=n) { printf("-1\n"); return ; } } } } } int ans=dis[n]; if(ans==inf) ans=-2; printf("%d\n",ans); } int main() { memset(head,-1,sizeof(head)); cnt=0; scanf("%d%d%d",&n,&ml,&md); for(int i=1;i<=ml;++i) { int a,b,d; scanf("%d%d%d",&a,&b,&d); add(a,b,d); } for(int i=1;i<=md;++i) { int a,b,d; scanf("%d%d%d",&a,&b,&d); add(b,a,-d); } spfa(); return 0; }
