Jimmy 落到一个平台后，要么向左，要么向右，对于任意一个平台都是这样。如果知道了 Jimmy 落到某一平台后的位置，向左或者向右到另外一个平台，这样就产生了两个子问题，这两个子问题与原问题是一样的。所以我们只需求从平台的左、右端点到地面的最短时间。

dp[i][0] 表示第 i 个平台左端点到地面的最短时间，dp[i][1] 表示第 i 个平台右端点到地面的最短时间。

将所有平台按高度从低到高的顺序排列。对于第 i 个平台的左端点，找到的第一个比 i 平台要低，且左端点在这个平台上的话，就有 dp[i][0] = min(e[i].l - e[j].l + dp[j][0], e[j].r - e[i].l + dp[j][1]) + e[i].h - e[j].h。右端也类似。
如果没有找到哪个平台比 i 平台要低，就看看能不能直接到地面，能的话dp[i][0]就是等于平台到地面的距离。

链接：http://poj.org/problem?id=1661

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1005;
const int M = 20005;
struct edge {
  int l, r, h;
  bool operator < (const edge &a) const {
    return h < a.h;
  }
} e[N];
int dp[N][2];
int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, x, y, mx;
    scanf("%d %d %d %d", &n, &x, &y, &mx);
    for (int i = 1; i <= n; i++) {
      scanf("%d %d %d", &e[i].l, &e[i].r, &e[i].h);
    }
    sort(e + 1, e + n + 1);
    memset(dp, INF, sizeof(dp));
    for (int i = 1; i <= n; i++) {
      bool flag_l = 0, flag_r = 0;
      for (int j = i - 1; j >= 1; j--) {
        if (e[i].h - e[j].h > mx)
          continue;
        if (e[j].l <= e[i].l && e[i].l <= e[j].r && !flag_l) {
          flag_l = 1;
          dp[i][0] = min(e[i].l - e[j].l + dp[j][0], e[j].r - e[i].l + dp[j][1]) + e[i].h - e[j].h;
        }
        if (e[j].l <= e[i].r && e[i].r <= e[j].r && !flag_r) {
          flag_r = 1;
          dp[i][1] = min(e[i].r - e[j].l + dp[j][0], e[j].r - e[i].r + dp[j][1]) + e[i].h - e[j].h;
        }
        if (flag_l && flag_r)
          break;
      }
      if (!flag_l && e[i].h <= mx) {
        dp[i][0] = e[i].h;
      }
      if (!flag_r && e[i].h <= mx) {
        dp[i][1] = e[i].h;
      }
    }
    int m = n;
    while (m > 0) {
      if (e[m].l <= x && x <= e[m].r && y >= e[m].h)
        break;
      m--;
    }
    if (m == 0) {
      printf("%d\n", y);
    } else {
      printf("%d\n", min(x - e[m].l + dp[m][0], e[m].r - x + dp[m][1]) + y - e[m].h);
    }
  }
  return 0;
}