题意：给个n个不同的高度，一个人从最低点跳跃，每次可以跳到第一个比它高的位置，最后跳到最高点，然后每次最多可以跳的距离为D，而且在跳跃时可以在不改变给定顺序的情况下移动这些高度，使得最后起始点和终点的位置最远，
思路：自己想了一会，想的方向错了，我自己想的方法是将最小高度记为0，最大高度记为n-1，然后写查分约束方程，这了一会发现条件不足，没想法了，看了大牛们的解法发现原来以给定的顺序直接进行条件就可以了，而且好简单，因为我们不能调整给定的顺序，那么对于给定的顺序就可以有pos(i+1)>=pos(i)+1，那么可以写出一个条件就是i+1–>i连一条权值为-1的边，还有一个条件是相邻两个要跳跃的距离不可以大于D，可以写出另一个方程，而现在条件全部是基于给定的序列，那么剩下的条件也要在这个基础进行，右面的点一定是在左边的点的后面，那么式子也就很好列出来了，图建完了，查询距离就用SPFA判环并输出就行了，有一点小问题就是建边的方向和跳跃的方向不同，我们要保证是向一个方向建图的，为什么这样呢，比如举个栗子，与例1类似，4 4，10 30 20 40这组的话10到20，跳跃的顺序是10 20 30 40，但是如果也是按照这个顺序建边的话，那么你将无法知道10的右面是谁到底是20还是30，找不到既定的顺序，所以只能这样建边，那么随之而来的问题就是，1和n的位置关系，如果1在n的左面那么肯定是从1到n跑spfa，因为我是从左到右建边的，1在n右面的话，也就是从n到1跑最短路了，这块要注意一下

#include <iostream>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int maxn=1010;
const int INF=0x3f3f3f3f;
struct sa
{int val;int id;
} a[maxn];
int cmp(sa x,sa y)
{return x.val<y.val;
}
struct EdgeNode
{int to;int w;int next;
};
EdgeNode edges[maxn*maxn];
int N,M;
int head[maxn],edge;
bool vis[maxn];
queue<int>que;
int dis[maxn],cnt[maxn];
void addedge(int u,int v,int c)
{edges[edge].w=c;edges[edge].to=v;edges[edge].next=head[u];head[u]=edge++;
}
void init()
{memset(a,0,sizeof(a));memset(cnt,0,sizeof(cnt));memset(vis,0,sizeof(vis));memset(dis,0,sizeof(dis));memset(head,-1,sizeof(head));edge=0;
}
bool spfa(int s,int n)
{int u;for(int i=0; i<=n; i++)dis[i]=INF;memset(vis,0,sizeof(vis));while(!que.empty())que.pop();que.push(s);vis[s]=true;dis[s]=0;memset(cnt,0,sizeof(cnt));cnt[s]=1;while(!que.empty()){u=que.front();que.pop();vis[u]=false;for(int i=head[u]; i!=-1; i=edges[i].next){int v=edges[i].to;int w=edges[i].w;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(!vis[v]){vis[v]=true;que.push(v);if(++cnt[v]>=n)return false;}}}}return true;
}
int main()
{int T,n,d;cin>>T;int Case=0;while(T--){init();cin>>n>>d;for(int i=1; i<=n; i++){cin>>a[i].val;a[i].id=i;}for(int i=1;i<n;i++)addedge(i+1,i,-1);sort(a+1,a+1+n,cmp);for(int i=1; i<n; i++){//addedge(i+1,i,-1);if(a[i].id<a[i+1].id)addedge(a[i].id,a[i+1].id,d);elseaddedge(a[i+1].id,a[i].id,d);//只能从一个方向往另一个方向加边}cout<<"Case "<<++Case<<": ";bool flag=1;int first, second;if(a[1].id<a[n].id){first=a[1].id;second=a[n].id;}else{first=a[n].id;second=a[1].id;}flag=spfa(first,n);if(flag==false)cout<<-1<<endl;else{cout<<dis[second]<<endl;//这里要输出的是n到1的距离，但是second不能换成n，因为排过序了，n不一定是原来的顺序，所以要用id，这块也要注意一下}}return 0;
}