看完题目第一遍，感觉很简单。当写完程序跑测试用例的时候，发现第二个总是过不了，然后好好研究了一下测试用例，才知道原来不是程序有问题，而是我的建图方式错了。对于这些无序的点，如果高的在右边，不等式是dis[tall]-dis[short]<=d；如果高的在左边，那么不等式就要变成dis[short]-dis[tall]<=d了。
另一个条件就是1<= dis[i+1]-dis[i] <=d；
一定要选最高的和最低的两个点其中最靠左边的作为源点，那么求一次最短路的意义就是另一个点到它的最远距离。
看代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define Maxn 1010
#define inf 0x7fffffff
#define Maxm Maxn*Maxn
using namespace std;
int dis[Maxn],index[Maxn],vi[Maxn],e,n;
struct Edge{
int to,next,val,from;
}edge[Maxm];
struct Point{
int num,val;
}p[Maxn];
void init()
{
memset(vi,,sizeof(vi));
memset(index,-,sizeof(index));
e=;
for(int i=;i<=n;i++)
{
dis[i]=inf;
}
}
void addedge(int from, int to ,int val)
{
edge[e].to=to;
edge[e].from=from;
edge[e].val=val;
edge[e].next=index[from];
index[from]=e++;
}
int bellman_ford(int u)
{
int i,j,temp,flag;
dis[u]=;
for(i=;i<=n;i++)
{
flag=;
for(j=;j<e;j++)
{
temp=edge[j].from;
if(dis[temp]<inf&&dis[temp]+edge[j].val<dis[edge[j].to])
{
dis[edge[j].to]=dis[temp]+edge[j].val;
flag=;
}
}
if(flag)
return ;
}
return ;
}
int cmp(Point a,Point b)
{
return a.val<b.val;
}
int main()
{
int i,j,t,d,Case=;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&d);
init();
for(i=;i<=n;i++)
{
scanf("%d",&p[i].val);
p[i].num=i;
}
for(i=;i<n;i++)
{
addedge(i+,i,-);
addedge(i,i+,d);
}
sort(p+,p+n+,cmp);
for(i=;i<n;i++)
{
if(p[i].num>p[i+].num)
{
addedge(p[i+].num,p[i].num,d);
addedge(p[i].num,p[i+].num,-);
}
else
{
addedge(p[i].num,p[i+].num,d);
addedge(p[i+].num,p[i].num,-);
} }
int u;
if(p[].num>p[n].num)
u=p[n].num;
else
u=p[].num;
if(bellman_ford(u))
printf("Case %d: %d\n",++Case,abs(dis[p[n].num]-dis[p[].num]));
else
printf("Case %d: -1\n",++Case);
//for(i=1;i<=n;i++)
//cout<<dis[i]<<" ";
//cout<<endl;
}
return ;
}