/*

【过滤这一段~~~】

一开始想的【错误的，为自己的总结的写的，读者略过】：

每个状态的点肯定是高度，那么我DP每一层，这样的话就有一层循环，其实这无关复杂度，不会很多时间

错误的是想法是从最高层开始DP下来，或者其实这样也同样可行，最高点是固定的。

OK，那么中间呢？怎么考虑一段，我们的目标且只能站在平台上，所以DP每个位置是不现实也是错误的想法。

最终只需要考虑两端？其实对啊，真的就只要两端考虑一下就好了！！！中间何必呢，自找麻烦，如果我是

sort了从高到低其实也好写，但是错就错在DP的位置是每一米的高度，如果这个高度没有平台，那不就是自找没趣？

所以我每次就以平台作为目标，因为平台是不会重叠，那么对象就看做平台好了。

*/

因为现在还很弱，这种左右分开DP真的太难想到了，当然也没有去仔细想，急着想水过去，就看了题解。【这样是不对的】

解析：

对象就是每一段平台，然后添两个平台，一个是地面，一个是最高点。排序由高度从小到大，所以处理的是从最低到最高的DP

当我掉在平台上的时候，我只能左走，或右走，走到左右两端的时间是好算的，

那么DP左右点的时间就是取复合要求的那些平台的DP值加上高度值和平移值；

第一：题目有要求，两个平台的高度不能超过max，

第二题目也有条件，高度各不相同，那么我们排序过以后，也就是说数组下标小的那些平台的高度一定是比他低的。

第三：他的下落点肯定是夹在接着的平台两端里面。

第四：我们一旦比他低的平台的，状态转移好就好结束，因为。。。自己想。。。

第五：他的下面可能没找什么平台，题目有解，那么就是他的高度呗。

状态转移方程不写了。。。。。后面其实写写真的很轻松了。

简述：

存入每一段，排序一下

然后for一层，哦，DP是DP[i][0]代表第i段左端的最少时间/DP[i][1]第i段右端最短的时间。

左右两端都要DP一下，DP的条件啊，转化啊，都说了，巨巨自己写写吧！！！加油！！！

参考的大牛博客： http://blog.csdn.net/jdplus/article/details/19919531

#include<iostream>

#include<cstdio>

#include<math.h>

#include<queue>

#include<map>

#include<stdlib.h>

#include<string>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

const int N=1e4+10;

int dp[N*4][4];

struct asd{

    int x1,x2;

    int h;

};

asd q[1010];

int n,tp;

bool cmp(asd z,asd x)

{

    if(z.h<x.h)

        return 1;

    return 0;

}

void left_t(int i)

{

    int k=i-1;

    while(k>0&&(q[i].h-q[k].h)<=tp){

        if(q[i].x1>=q[k].x1&&q[i].x1<=q[k].x2){

            dp[i][0]=(q[i].h-q[k].h)+min(q[i].x1-q[k].x1+dp[k][0],q[k].x2-q[i].x1+dp[k][1]);

        return;

        }

        else

            --k;

    }

    if((q[i].h-q[k].h)>tp)

        dp[i][0]=INF;

    else

        dp[i][0]=q[i].h;

}

void right_t(int i)

{

    int k=i-1;

    while(k>0&&(q[i].h-q[k].h)<=tp){

        if(q[i].x2<=q[k].x2&&q[i].x2>=q[k].x1){

            dp[i][1]=(q[i].h-q[k].h)+min(q[i].x2-q[k].x1+dp[k][0],q[k].x2-q[i].x2+dp[k][1]);

            return;

        }

        else

            --k;

    }

    if((q[i].h-q[k].h)>tp)

        dp[i][1]=INF;

    else

        dp[i][1]=q[i].h;

}

int smallest()

{

    int i,j;

    for(int i=1;i<=n+1;i++){

        left_t(i);

        right_t(i);

    }

    return min(dp[n+1][0],dp[n+1][1]);

}

int main()

{

    int T,k;

    int x0,y0,i,j;

    cin>>T;

    while(T--){

        cin>>n>>x0>>y0>>tp;

        for(int i=1;i<=n;i++){

            scanf("%d%d%d",&q[i].x1,&q[i].x2,&q[i].h);

        }

        q[0].h=0;

        q[0].x1=-20000;

        q[0].x2=20000;

        q[n+1].h=y0;

        q[n+1].x1=x0;

        q[n+1].x2=x0;

        sort(q,q+n+2,cmp);

        printf("%d\n",smallest());

    }

    return 0;

}