总时间限制:

1000ms

内存限制:

65536kB

描述

"Help Jimmy" 是在下图所示的场景上完成的游戏。

场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。

Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。

设计一个程序，计算Jimmy到底地面时可能的最早时间。

输入

第一行是测试数据的组数t（0 <= t <= 20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接下来的N行每行描述一个平台，包括三个整数，X1[i]，X2[i]和H[i]。H[i]表示平台的高度，X1[i]和X2[i]表示平台左右端点的横坐标。1 <= N <= 1000，-20000 <= X, X1[i], X2[i] <= 20000，0 < H[i] < Y <= 20000（i = 1..N）。所有坐标的单位都是米。

Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保证问题一定有解。

输出

对输入的每组测试数据，输出一个整数，Jimmy到底地面时可能的最早时间。

样例输入

1
3 8 17 20
0 10 8
0 10 13
4 14 3

样例输出

23

AC代码：

#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#pragma warning(disable:4996)
using namespace std;
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<unordered_map>
#include<unordered_set>
const int maxn = 1000 + 10;
const int INF = 0x3f3f3f3f;//若为7ffffff则相加时会越界，然后WA！！
struct plate {
	int x1, x2, h;
}p[maxn];
int dp[maxn][2], n, max_high;
bool cmp(plate &x, plate &y) {
	return x.h < y.h;
}
void lefttime(int i) {
	int k = i - 1;
	while (k > 0 && p[i].h - p[k].h <= max_high) {
		if (p[k].x1 <= p[i].x1&&p[k].x2 >= p[i].x1) {
			dp[i][0] = (p[i].h - p[k].h) + min(dp[k][0] + p[i].x1 - p[k].x1, dp[k][1] + p[k].x2 - p[i].x1);
			return;
		}
		else k--;
	}
	if (p[i].h - p[k].h > max_high)dp[i][0] = INF;
	else dp[i][0] = p[i].h;
}


void righttime(int i) {
	int k = i - 1;
	while (k > 0 && p[i].h - p[k].h <= max_high) {
		if (p[k].x1 <= p[i].x2&&p[k].x2 >= p[i].x2) {
			dp[i][1] = (p[i].h - p[k].h) + min(dp[k][0] + p[i].x2 -p[k].x1 , dp[k][1] + p[k].x2 - p[i].x2);
			return;
		}
		else k--;
	}
	if (p[i].h - p[k].h > max_high)dp[i][1] = INF;
	else dp[i][1] = p[i].h;
}


int min_time() {
	for (int i = 1; i <= n + 1; i++) {
		lefttime(i);
		righttime(i);
	}
	return min(dp[n + 1][0], dp[n + 1][1]);
}


int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		scanf("%d%d%d", &p[n + 1].x1, &p[n + 1].h, &max_high);
		p[n + 1].x2 = p[n + 1].x1;
		p[0].x1 = -20000;
		p[0].x2 = 20000;
		p[0].h = 0;
		for (int i = 1; i <= n; i++)
			scanf("%d%d%d", &p[i].x1, &p[i].x2, &p[i].h);
		sort(p, p + n + 1, cmp);
		printf("%d\n", min_time());
	}
	return 0;
}