月球上反凤凰装甲在凤凰之力附身霍普之前，将凤凰之力打成五份，分别附身在X战警五大战力上面辐射眼、白皇后、钢力士、秘客和纳摩上（好尴尬，汗）。 在凤凰五使徒的至高的力量的威胁下，复仇者被迫逃到昆仑的一座山上，因为凤凰五使徒监视不到那里。 霍普加入了复仇者，为了磨练自己，她在n个山峰之间跳跃。 这n个山峰在一条直线上，每个山峰都有不同的高度，只知道这些山峰的相对位置。霍普可以将这些山峰左右移动但不能改变他们的相对位置（要保证两两山峰间距为整数且大于等于1）。霍普要从最矮的山峰开始跳，每次跳向第一个比现在她所在的山峰高的山峰，一共跳n-1次，由于能力有限，每次跳跃的水平距离小于等于d。 霍普想知道如何移动这些山峰，使得在可以经过所有的山峰并跳到最高的山峰上的基础下，又要使最矮的山峰和最高的山峰的水平距离最远，霍普要你求出最远的水平距离。如果无论如何也不能经过所有的山峰并跳到最高的山峰上，那么输出-1。
思路：差分约束系统。 把这道题目分解，可以分解为两个条件。 1、两个山峰之间水平距离至少为1(因为山峰不能再同一位置上)。 2、霍普每次最多跳d的水平距离。 对于第一个条件，对于两个相邻的山峰，相对位置（即输入顺序）大的向相对位置小的连一条-1的边。 对于第二个条件，对于两个高度排名相邻的山峰，相对位置小的向相对位置大的连一条d的边。 然后比较最高和最低的山峰，从相对位置小的那个山峰出发，做一次最短路，输出到相对位置大的山峰的距离。
#include <cmath> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <queue> const long long maxlongint=2147483647; const long long mo=1000000007; const long long N=2005; using namespace std; struct ddx { int h,p; }a[N]; int T,last[N*2],to[N*2],ne[N*2],v[N*2],dis[N],n,dd,tot,d[N*N],pp,num[N]; bool bz[N]; void bj(int x,int y,int z) { ne[++tot]=last[x]; last[x]=tot; to[tot]=y; v[tot]=z; } bool cmp(ddx x,ddx y) { return x.h<y.h; } int spfa(int x) { memset(bz,true,sizeof(bz)); fill(dis,dis+1+n,1200000000); memset(num,0,sizeof(num)); int head=0,tail=1,g; dis[x]=0; d[1]=x; while(head<tail) { g=d[++head]; bz[g]=true; for(long long i=last[g];i;i=ne[i]) { long long j=to[i]; if(dis[j]>dis[g]+v[i]) { dis[j]=dis[g]+v[i]; if(bz[j]) { bz[j]=false; d[++tail]=j; if(++num[j]>n) return -1; } } } } return 0; } int main() { scanf("%d",&T); while(T--) { pp++; scanf("%d%d",&n,&dd); tot=0; memset(last,0,sizeof(last)); memset(ne,0,sizeof(ne)); memset(to,0,sizeof(to)); memset(v,0,sizeof(v)); for(int i=1;i<=n;i++) { scanf("%d",&a[i].h); a[i].p=i; bj(i,i-1,-1); } sort(a+1,a+1+n,cmp); for(int i=1;i<=n-1;i++) { if(a[i].p<a[i+1].p) bj(a[i].p,a[i+1].p,dd); else bj(a[i+1].p,a[i].p,dd); } int e,k; if(a[1].p<a[n].p) { k=spfa(a[1].p); e=a[n].p; } else { k=spfa(a[n].p); e=a[1].p; } if(k==-1) printf("-1\n"); else { printf("%d\n",dis[e]); } } }