题意：有n栋房子，给出每栋房子的高度和开始时的相对位置，可以移动一些房子，但不能改变这些房子的相对位置，现在从最矮的房子开始，每次跳至比它高的第一栋房子， 而且每次跳跃的水平距离最大是D，房子不能在同一位置，只能在整点位置。问最矮的房子和最高的房子之间的最大距离可以是多少？如果不能从最矮的房子到达最高的房子则输出-1.
分析：令d[i]表示第i栋房子与第一栋房子之间的最大距离，那么我们要求的就是的的d[n],求最短路即可，首先每栋房子之间的相对位置已经确定且不能在同一位置，那么d[i 1] > d[i],每次要跳至比它高的房子上，那么我们需要对房子按高度排序。因为开始时已经规定标号小的点在标号大的点的左边，这样，我们如果从标号大的点到标号小的点，建一条这样的边就会有问题，只能按小到大建边，而且如果两个排序后相邻房子之间的标号大于D的话则不可能到最高的房子，因为房子不可能在同一位置，他们之间的距离至少是D。约束条件只有这两者，建边时需要处理一下方向。最后如果最高的房子标号比矮的房子小的话，则以最高的房子为源点进行spfa，如果存在负环则输出-1.
杭电炸了。。。放个std
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int N = 1010, M = 10000;
const int INF = 0x3f3f3f3f;
struct house{
int he, id;
bool operator < (const house& x)const { return he < x.he; }
}h[N];
struct edge{
int v, d, next;
edge(int v, int d, int n):v(v), d(d), next(n){}
edge(){}
}ed[M];
int head[N], d[N], vis[N], cnt[N];
int n, s, e, k;
queue<int> q;
void init() {
k = 0;
memset(head, -1, sizeof(int) * n);
memset(d, INF, sizeof(int) * n);
memset(vis, 0, sizeof(int) * n);
memset(cnt, 0, sizeof(int) * n);
for (int i = 0; i < n; i ) h[i].id = i;
while (!q.empty()) q.pop();
}
void add(int u, int v, int d) {
ed[k] = edge(v, d, head[u]);
head[u] = k ;
}
int spfa() {
d[s] = 0; cnt[s] ;
q.push(s);
while (!q.empty()) {
int x = q.front(); q.pop();
vis[x] = 0;
for (int i = head[x]; i != -1; i = ed[i].next) {
int t = ed[i].v;
if (d[t] > d[x] ed[i].d) {
d[t] = d[x] ed[i].d;
if (!vis[t]) {
vis[t] = 1; q.push(t);
if ( cnt[t] > n) return -1;
}
}
}
}
return d[e];
}
int main() {
int t, ca = 0;
scanf("%d", &t);
while (t--) {
int d;
scanf("%d %d", &n, &d);
init();
for (int i = 0; i < n; i ) scanf("%d", &h[i].he);
sort(h, h n);
int flag = 1;
for (int i = 0; i < n-1 && flag; i ) {
add(i 1, i, -1);
int u = min(h[i].id, h[i 1].id), v = max(h[i].id, h[i 1].id);
if (v - u > d) flag = 0;
add(u, v, d);
}
s = min(h[0].id, h[n-1].id), e = max(h[0].id, h[n-1].id);
printf("Case %d: %dn", ca, flag ? spfa() : -1);
}
return 0;
} 
