本来是一道普通的差分约束题，结果特么的写完连样例都过不了。。。
后来才在差分约束的百度百科中现这段话：
1.如果将源点到各点的距离初始化为0，最终求出的最短路满足 它们之间相互最接近了；
2.如果将源点到各点的距离初始化为INF(无穷大)，其中之1为0，最终求出的最短路满足 它们与该点之间相互差值最大。
呵呵呵原来我是错在Dist的初始值这里啊。。。
于是第二次写……把起点的Dist设为0，其余都设为+∞
可是依旧过不了样例……
终于发现这句话的问题……差值最大……也就是说当终点在起点左边的时候我们可以知道Dist[t]-Dist[s]<0，Answer为Dist[s]-Dist[t]
然后差值最大是保证Dist[t]-Dist[s]最大，也就是保证Dist[s]-Dist[t]最小，那么Answer……
于是改成让Dist[min(s,t)]=0
接着又因为几次队列的初始化问题WA了几次。。。
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <deque>#define rep(i, l, r) for(int i = l; i <= r; i++)
#define down(i, l, r) for(int i = l; i >= r; i--)
#define N 1009
#define MAX 1<<30using namespace std;
inline int read()
{int x=0, f=1; char ch=getchar();while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }return x*f;
}struct edge{int y, z, n;} e[N*5]; int fir[N], en;
struct node{int h, id;} s[N];
int n, k, d[N], c[N], ans;
deque <int> q;
bool b[N];
bool cmp(node a, node b) { return a.h<b.h; }void Add(int x, int y, int z)
{en++, e[en].y = y, e[en].z = z, e[en].n = fir[x], fir[x] = en;
}int main()
{int t=read(), tt=t;while (t--){rep(i, 1, n) fir[i]=0; en=0; ans=0;if (tt-t == 41) en = 0;n=read(), k=read();rep(i, 1, n) s[i].h=read(), s[i].id=i;sort(s+1, s+1+n, cmp);rep(i, 1, n-1) s[i].id>s[i+1].id ? Add(s[i+1].id, s[i].id, k) : Add(s[i].id, s[i+1].id, k);rep(i, 1, n-1) Add(i+1, i, -1);rep(i, 1, n) b[i]=0, c[i]=0, d[i]=MAX;d[min(s[n].id, s[1].id)] = 0; q.push_front(min(s[n].id, s[1].id));while (!q.empty()){int x=q.front(), o=fir[x], y=e[o].y; q.pop_front(); b[x]=0;if (c[x] > n) { ans=-1; break; }while (o){if (d[y] > d[x]+e[o].z) {d[y] = d[x]+e[o].z;if (!b[y]) b[y]=1, c[y]++, !q.empty()&&d[y]<=d[q.front()] ? q.push_front(y) : q.push_back(y);}o=e[o].n, y=e[o].y;}}while (!q.empty()) q.pop_front();if (ans!=-1) ans=abs(d[s[1].id]-d[s[n].id]);printf("Case %d: %d\n", tt-t, ans);}return 0;
}
