#include <iostream.h>
#define MAXLONGINT 100000000;
const int MAXN = 1005; 

struct node{
	int x1, x2, h;	// x1 - left, x2 - right, h - height
};

int N, X, Y, MAX;
node Platform[MAXN];  
long f[MAXN][2];  
// f[i]记录Jimmy到第i个平台时的最小唯一，f[i][0]记录到该平台左端，f[i][1]记录到该平台右端

void Sort(){
	int i, j;
	node temp;
	for (i = 1; i <= N - 1; ++ i)
		for (j = i + 1; j <= N; j ++)
			if (Platform[i].h < Platform[j].h || 
				Platform[i].h == Platform[j].h && Platform[i].x1 > Platform[j].x1){
				temp = Platform[i];
				Platform[i] = Platform[j];
				Platform[j] = temp;
			}
}

// 纵向是常数，只对横向路程dp, 
void Solve(){ 
	int i, j, delta;
	for (i = 1; i <= N; ++ i)
		if (X >= Platform[i].x1 && X <= Platform[i].x2 && 
			(Y - Platform[i].h) >= 0 && (Y - Platform[i].h) <= MAX)
			break;
	f[i][0] = X - Platform[i].x1; // 找到Jimmy能到达的第一个平台
	f[i][1] = Platform[i].x2 - X;
	int ii = i;
	for (; i <= N; i++)
		for (j = ii; j < i; j ++){
			delta = Platform[j].h - Platform[i].h;
			if (delta <= MAX && delta > 0){
				if (Platform[j].x1 >= Platform[i].x1 && Platform[j].x1 <= Platform[i].x2){
					if (f[j][0] + Platform[j].x1 - Platform[i].x1 < f[i][0])
						f[i][0] = f[j][0] + Platform[j].x1 - Platform[i].x1;
					if (f[j][0] + Platform[i].x2 - Platform[j].x1 < f[i][1])
						f[i][1] = f[j][0] + Platform[i].x2 - Platform[j].x1;
				};
				if (Platform[j].x2 >= Platform[i].x1 && Platform[j].x2 <= Platform[i].x2){
					if (f[j][1] + Platform[j].x2 - Platform[i].x1 < f[i][0])
						f[i][0] = f[j][1] + Platform[j].x2 - Platform[i].x1;
					if (f[j][1] + Platform[i].x2 - Platform[j].x2 < f[i][1])
						f[i][1] = f[j][1] + Platform[i].x2 - Platform[j].x2;
				};
			}
		}
}

void Print(){
	long ans = MAXLONGINT;
	int i, H = Platform[N].h;
	i = N;
	while (true){
		if (i < 1 || Platform[i].h != H) break;
		if (f[i][0] < ans)
			ans = f[i][0];
		if (f[i][1] < ans)
			ans = f[i][1];
		i --;
	}
	ans += Y;  // 加上y方向的路程
	cout << ans << endl;
}

void main(){
	int t, i;
	cin >> t;
	while (t --){
		cin >> N >> X >> Y >> MAX;
		for (i = 1; i <= N; i ++){
			f[i][0] = MAXLONGINT;
			f[i][1] = MAXLONGINT;
		}
		for (i = 1; i <= N; i ++)
			cin >> Platform[i].x1 >> Platform[i].x2 >> Platform[i].h;
		Sort();
		Solve();
		Print();
	}
}
	

• Re:I am confused ... why WA? (2496) Akvdynaxic 2006-04-06 20:36:02