f[i][0]:从i平台左端跳下到地面的最短时间(不包括竖直距离)
f[i][1]:从j平台右端跳下到地面的最短时间(不包括竖直距离)
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;
struct level {
int x1, x2, h;
} a[1005];
bool cmp(level a, level b) { return a.h > b.h; }
long long f[1005][2];
int main() {
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T, N, X, Y, MAX;
cin >> T;
while (T--) {
cin >> N >> X >> Y >> MAX;
for (int i = 1; i <= N; i++) {
cin >> a[i].x1 >> a[i].x2 >> a[i].h;
}
//起点
a[0].x1 = X;
a[0].x2 = X;
a[0].h = Y;
//地面
a[N + 1].x1 = -INF;
a[N + 1].x2 = INF;
a[N + 1].h = 0;
sort(a + 1, a + 1 + N, cmp); //从高到低排序
for (int i = N; i >= 0; --i) {
int j;
//从i的左端跳下
for (j = i + 1; j <= N + 1; ++j) {
if (a[j].x1 <= a[i].x1 && a[i].x1 <= a[j].x2) {
break;
}
}
if (j == N + 1) {
if (a[i].h <= MAX)
f[i][0] = 0;
else
f[i][0] = INF;
} else {
if (a[i].h - a[j].h <= MAX) {
int t1 = a[i].x1 - a[j].x1 + f[j][0];
int t2 = a[j].x2 - a[i].x1 + f[j][1];
f[i][0] = min(t1, t2);
} else
f[i][0] = INF;
}
//从i的右端跳下
for (j = i + 1; j <= N + 1; ++j) {
if (a[j].x1 <= a[i].x2 && a[i].x2 <= a[j].x2) {
break;
}
}
if (j == N + 1) {
if (a[i].h <= MAX)
f[i][1] = 0;
else
f[i][1] = INF;
} else {
if (a[i].h - a[j].h <= MAX) {
int t1 = a[i].x2 - a[j].x1 + f[j][0];
int t2 = a[j].x2 - a[i].x2 + f[j][1];
f[i][1] = min(t1, t2);
} else
f[i][1] = INF;
}
}
cout << f[0][0] + Y << endl;
}
return 0;
}