HDU3440 House Man

#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: %d\n", ++ca, flag ? spfa() : -1);  
    }  
    return 0;  
}