典型的记忆化搜索问题，dfs一遍即可。但是不知道WA在哪里了= =，一直都没找出错误。因为思路是很简单的，肯定是哪里写挫了，因此不再继续追究了。
WA的代码如下，希望日后有一天能找出错误= =：
————————————————灵光一闪的分界线——————————————————
在写博客的时候突然灵光一闪，想到了错在哪里了= =。总的来说还是考虑问题不周导致的。AC代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = + ;
const int inf = 0x3f3f3f3f; int n,x,y,limit;
int left[N],right[N],h[N];
int L_nxt[N],R_nxt[N];
void find(int u)
{
int L = -, R = -;
for(int i=;i<=n;i++)
{
if(u == i || h[i] >= h[u]) continue;
if(left[u] >= left[i] && left[u] <= right[i])
{
if(L == -) L = i;
else if(h[i] > h[L]) L = i;
}
if(right[u] >= left[i] && right[u] <= right[i])
{
if(R == -) R = i;
else if(h[i] > h[R]) R = i;
}
}
if(L == -)
{
if(h[u] > limit) L_nxt[u] = -; // 表示不能往这个方向跳下
else L_nxt[u] = -; // 表示可以到地面
}
else if(h[u] - h[L] > limit) L_nxt[u] = -;
else L_nxt[u] = L; if(R == -)
{
if(h[u] > limit) R_nxt[u] = -; // 表示不能往这个方向跳下
else R_nxt[u] = -; // 表示可以到地面
}
else if(h[u] - h[R] > limit) R_nxt[u] = -;
else R_nxt[u] = R;
} struct node
{
int L, R;
void init() {L = R = inf;}
};
bool vis[N];
node dp[N];
node dfs(int u)
{
if(vis[u]) return dp[u];
vis[u] = ;
node ans; ans.init();
if(L_nxt[u] != -)
{
if(L_nxt[u] == -) ans.L = h[u];
else
{
node temp = dfs(L_nxt[u]);
ans.L = min(ans.L, h[u] - h[L_nxt[u]] + min(left[u] - left[L_nxt[u]] + temp.L, right[L_nxt[u]] - left[u] + temp.R));
}
} if(R_nxt[u] != -)
{
if(R_nxt[u] == -) ans.R = h[u];
else
{
node temp = dfs(R_nxt[u]);
ans.R = min(ans.R, h[u] - h[R_nxt[u]] + min(right[u] - left[R_nxt[u]] + temp.L, right[R_nxt[u]] - right[u] + temp.R));
}
}
return dp[u] = ans;
} int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&n,&x,&y,&limit);
for(int i=;i<=n;i++) scanf("%d%d%d",left+i,right+i,h+i);
for(int i=;i<=n;i++) find(i);
memset(vis,false,sizeof vis); int root = -;
for(int i=;i<=n;i++)
{
if(x >= left[i] && x <= right[i])
{
if(root == -) root = i;
else if(h[root] < h[i]) root = i;
}
}
// root为-1的话dfs会出错的，因此要特判
if(root == -) {printf("%d\n",y); continue;} dfs(root);
int ans = y - h[root] + min(x - left[root] + dp[root].L, right[root] - x + dp[root].R);
printf("%d\n",ans);
}
return ;
}