题目描述：  “是男人就下100层”游戏，给你地图信息，问你最短能多长时间到达地面。

DP，  先把各个平台按高度排序，由高到低。

vst[i][j][k] = 1  表示第i个平台的j端与第k个平台可通（高度不超max，垂直下落，并且之间没有其他平台阻拦） 其中 0<= i <= n, k > i, j = 0表示左端，j = 1表示右端。

dp[i][j]表示到达第i个平台的j端最少需要多少时间。

状态转移：

dp[i][j] = min(vst[k][0][j] && dp[k][0] judge(k0->j), vst[k][1][j] && dp[k][1] judge(k1 -> j)  0<= k < i

代码：

#include<iostream>
#include<algorithm>
using namespace std;
int t, n, a, b, mm, dp[1002][2], ans;
bool vst[1002][2][1002];
struct edge
{
    int len[2], h;
}x[1002];
bool cmp(edge aa, edge bb)
{
    return aa.h > bb.h;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d%d", &n, &a, &b, &mm);
        for(int i = 0; i < n; i )
            scanf("%d%d%d", &x[i].len[0], &x[i].len[1], &x[i].h);
        x[n].len[0] = x[n].len[1] = a, x[n].h = b;n ;
        x[n].len[0] = -30000, x[n].len[1] = 30000, x[n].h = 0;n ;
        sort(x, x n, cmp);
        ans = 2000000000;
        memset(dp, 0, sizeof(dp));memset(vst, 0, sizeof(vst));
        for(int i = 0; i < n; i )
            for(int j = 0; j < 2; j )
            {
                bool flag = true;
                for(int k = i 1; k < n && flag; k )
                    if (x[i].h - x[k].h <= mm)
                    {
                        if (x[i].len[j] < x[k].len[1] && x[i].len[j] > x[k].len[0])
                        {
                            flag = false;
                            vst[i][j][k] = 1;
                        }
                        else if (x[i].len[j] == x[k].len[0] || x[i].len[j] == x[k].len[1])
                            vst[i][j][k] = 1;
                    }
                    else
                        flag = false;
            }
        if (vst[0][0][n - 1]) ans = 0;
        for(int i = 1; i < n - 1; i )
        {
            int l, r;
            l = r = 2000000000;
            for(int j = 0; j < 2; j )
                for(int k = 0; k < i; k )
                    if (vst[k][j][i])
                    {
                        if (dp[k][j] x[i].len[1] - x[k].len[j] < r)
                            r = dp[k][j] x[i].len[1] - x[k].len[j];
                        if (dp[k][j] x[k].len[j] - x[i].len[0] < l)
                            l = dp[k][j] x[k].len[j] - x[i].len[0];
                    }
            dp[i][0] = l, dp[i][1] = r;
            if (vst[i][0][n - 1] && dp[i][0] < ans)
                ans = dp[i][0];
            if (vst[i][1][n - 1] && dp[i][1] < ans)
                ans = dp[i][1];
        }
        printf("%d\n", ans b);
    }
    return 0;
}