GESP 题解库 / 8 级题解 / [GESP202406 八级] 空间跳跃 · 第 15 / 24 题
GESP202406 八级 · P10726 · 困难

空间跳跃

把状态压缩成每块挡板的左右端点(共 2n 个点),掉落边带上"落到板内再走到端点"的代价,跑 Dijkstra。

🧱
n ≤ 1000
挡板数量
📐
lᵢ, rᵢ, hᵢ ≤ 10⁵
坐标与高度
⚡
O(n² + n log n)
找落点 + Dijkstra
🎯
端点状态 + 掉落边
核心建模
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨在二维空间中有 n 个水平挡板,并且挡板之间彼此不重叠,其中第 i 个挡板处于水平高度 hᵢ,左右端点分别位于 lᵢ 与 rᵢ。

小杨可以在挡板上左右移动,当小杨移动到右端点时,如果再向右移动会竖直掉落,从而落到下方第一个挡板上,移动到左端点时同理。小杨在挡板上每移动 1 个单位长度会耗费 1 个单位时间,掉落时每掉落 1 个单位高度也会耗费 1 个单位时间。

小杨想知道,从第 s 个挡板上的左端点出发到第 t 个挡板需要耗费的最少时间是多少?

注意:可能无法从第 s 个挡板到达到第 t 个挡板。

输入格式

第一行一个正整数 n,代表挡板数量。

第二行两个正整数 s, t,含义如题面所示。

之后 n 行,每行三个正整数 lᵢ, rᵢ, hᵢ,代表第 i 个挡板。

输出格式

输出一个整数代表需要耗费的最少时间;如果无法到达则输出 −1。

样例

样例输入输出
#13
3 1
5 6 3
3 5 6
1 4 100000
100001
💡
人话翻译:挡板就是一层层"平台",你只能在平台上左右走;走到端点再往外迈一步就会垂直掉下去,落到正下方第一块挡板上(如果正下方没有平台,就掉出系统,这条路走不通)。
起点是第 s 块挡板的左端点;终点是第 t 块挡板的任意一点(踩上它就算到)。
关键观察:任何有意义的"落脚点"只有每块挡板的左右端点——因为在板中间停下来没有任何好处,要么继续走到某个端点准备掉落,要么这里就是终点。
于是把状态压缩成 2n 个点,在它们之间连边(同板内左右互通 + 端点向外掉落),跑一次 Dijkstra 就得到答案。

🔍 关键词提取

图论建模Dijkstra 最短路状态压缩到端点掉落边不可达输出 −1

已知条件

项目说明
输入第一行 n;第二行 s、t;随后 n 行每行 lᵢ、rᵢ、hᵢ
输出最少时间;不可达输出 −1
数据范围1 ≤ n ≤ 1000,1 ≤ lᵢ ≤ rᵢ ≤ 10⁵,1 ≤ hᵢ ≤ 10⁵
移动代价水平 1 单位 = 1;竖直下落 1 单位 = 1
掉落规则从端点向外 → 落到正下方第一个挡板;下方没有则掉出系统
特殊子任务20% 满足 lᵢ = 1;40% 满足 lᵢ = i, rᵢ = i + 1;40% 无特殊限制

需要解决的问题

02
思维导图
整理解题思路的全貌
🧱 状态 = 端点,边 = 横走 + 掉落
🧠 状态设计
(i, 左) 与 (i, 右),共 2n 个点
起点 (s, 左),距离 0
终点:任意能掉到 t 的候选取最小
板中间不必落状态
🔗 两类边
同板:左 ↔ 右,权 rᵢ − lᵢ
左端点掉落:→ (m, 左) 与 (m, 右)
右端点掉落:→ (m, 左) 与 (m, 右)
掉落边权 = 掉落高度 + 板内横走距离
🔍 找落点 m
在坐标 x 处向下看
取满足 h < hᵢ 且 l <= x <= r 的最高挡板
O(n) 扫描即可,共 2n 次
找不到则这个方向掉出系统
⚠️ 易错点
漏掉"落点走到端点"的横走代价
从端点掉落时用了对方的坐标
s = t 忘记特判输出 0
距离用 int(最大可达 10⁵ 级)
03
样例手算推导
样例逐段拆解 + 状态图建边演示

🧮 样例 1 逐段拆解:3 → 2 → 1 共 100001

三块挡板:

编号区间 [l, r]高度 h说明
1[5, 6]3最矮,位于右侧
2[3, 5]6中间高度
3[1, 4]100000最高,起点所在

从第 3 块的左端点 x = 1, h = 100000 出发。题面给出的最优方案是"先向右走到端点,再掉到 2,再掉到 1"。

1
第 1 段:在挡板 3 上从 x = 1 走到右端点 x = 4

水平距离 4 − 1 = 3

耗时 3,位置变为 (x = 4, h = 100000)

顺便说明:如果此时向左走,x = 1 处下方没有任何挡板包含 1(挡板 2 是 [3, 5],挡板 1 是 [5, 6]),会直接掉出系统,所以只能往右

累计 3

2
第 2 段:从 x = 4 向右掉落

在 x = 4 处向下看,第一个与之相交的挡板是第 2 块([3, 5],h = 6)

掉落高度 100000 − 6 = 99994

落点为 (x = 4, h = 6),落在挡板 2 的内部

注意落点不是挡板 2 的端点,还得继续走

累计 3 + 99994 = 99997

3
第 3 段:在挡板 2 上从 x = 4 走到右端点 x = 5

水平距离 5 − 4 = 1

耗时 1,位置变为 (x = 5, h = 6)

为什么向右?因为 x = 5 下方只有挡板 1([5, 6])能接住,而挡板 1 正是终点

累计 99997 + 1 = 99998

4
第 4 段:从 x = 5 向右掉落到挡板 1

在 x = 5 处向下看,能接住的是第 1 块([5, 6],h = 3)

掉落高度 6 − 3 = 3

落到挡板 1 上即到达终点,不需要再走

✅ 累计 99998 + 3 = 100001

段动作代价累计
1挡板 3 上:x = 1 → x = 433
2x = 4 向右掉落:h = 100000 → h = 69999499997
3挡板 2 上:x = 4 → x = 5199998
4x = 5 向右掉落:h = 6 → h = 33100001
🔑
这个样例最容易被漏掉的是第 3 段的 "+1"。很多人的第一版写法只算"掉落高度",得到 99997,因为忽略了落点是板内一点、还得横走才能到端点。
把"落点 → 端点"的横走距离打包进掉落边权,就再也不会漏了。

🧮 状态图怎么建:只记端点,边权带上横走距离

把每块挡板拆成左端点状态与右端点状态,共 2n 个点。记 Lᵢ = lᵢ、Rᵢ = rᵢ、Hᵢ = hᵢ。

边从到权重含义
同板横走(i, 左)(i, 右)Rᵢ − Lᵢ在板 i 上走完整条板
同板横走(i, 右)(i, 左)Rᵢ − Lᵢ反向同理
左端掉落(i, 左)(m, 左)(Hᵢ − Hₘ) + (Lᵢ − Lₘ)m 是 Lᵢ 正下方第一块
左端掉落(i, 左)(m, 右)(Hᵢ − Hₘ) + (Rₘ − Lᵢ)落到 m 的中间后往右走到端点
右端掉落(i, 右)(m, 左)(Hᵢ − Hₘ) + (Rᵢ − Lₘ)m 是 Rᵢ 正下方第一块
右端掉落(i, 右)(m, 右)(Hᵢ − Hₘ) + (Rₘ − Rᵢ)落到 m 的中间后往右走到端点
1
第一步:找落点("正下方第一块")

对挡板 i 的左端点 x = Lᵢ:在所有 Hₘ < Hᵢ 且 Lₘ ≤ x ≤ Rₘ 的挡板里

取高度最大的那块 m(它就是下落时最先碰到的那块)

如果一块都没有,说明这个方向会掉出系统,不连边

落点唯一("互不重叠"的功劳)

2
第二步:把"落点 → 端点"的横走并进边权

落点坐标是端点的 x(比如 Lᵢ)

走到 m 左端点的距离 = Lᵢ − Lₘ

走到 m 右端点的距离 = Rₘ − Lᵢ

边权 = 掉落高度 (Hᵢ − Hₘ) + 横走距离

✅ 状态里就不用记录"板内位置"了

3
第三步:源点与 Dijkstra

源点 = (s, 左),dist = 0

跑堆优化 Dijkstra,得到所有 2n 个状态的最短距离

dist 全部就位

4
第四步:统计答案

若 s = t,答案 0(起点就在目标板左端点)

否则枚举每块 m:若从 m 的左端点掉落正好落到 t,候选值 = dist(m, 左) + (Hₘ − Hₜ)

右端点同理;所有候选取最小

一个候选都没有 → 输出 −1

✅ 得到最少时间或 −1

⚠️
三个必须写对的地方:① 掉落边要加横走距离——漏了就会算小(样例会得到 99997);② 落点坐标要用"掉落那一侧的端点"——从右端点掉就用 Rᵢ 去找 m,之后横走距离按 Rᵢ 与 Lₘ / Rₘ 计算,不要混用左端点;③ 统计答案时别忘 s = t,起点就在目标板上,答案是 0。
04
解法对比
端点状态 + Dijkstra(正解)vs 细粒度坐标建图

⚔️ 解法对比

🟢 端点状态 + Dijkstra(推荐) 推荐

每块挡板只保留左端点、右端点两个状态(2n 个点),掉落边权 = 掉落高度 + 落到板内后走到端点的横走距离

  • 点数 2n ≤ 2000,边数 O(n)
  • 找落点 O(n) 扫描,总建图 O(n²)
  • Dijkstra O(n log n)
  • 代码约 60 行
💡
为什么等价:板内任意两点间代价就是距离,而在板中间停留既不增加选择也不会更省时间,所以最优路径只会在端点处改变挡板;把"落点 → 端点"的距离折算进边权,状态里就不必再记录板内位置。

🟠 把每个单位坐标都当点

(挡板 i, 坐标 x)都建点,左右走 1 单位连一条权 1 的边,端点上连掉落边

  • 点数 Σ(rᵢ − lᵢ + 1),最坏约 10⁸ 个
  • 坐标上限 10⁵ × n = 1000 → 完全存不下
  • 正确性没问题,但时间和空间都爆炸
  • 可以当随机对拍用的暴力
⚠️
为什么不能用:lᵢ, rᵢ ≤ 10⁵、n ≤ 1000,把所有整数坐标都展开最坏是 10⁸ 个状态,内存直接爆掉。但它的正确性很直观,适合写小数据对拍程序。

📈 性能对比

方案状态数结论
端点状态 + Dijkstra2n ≤ 2000✅ 正确,本题正解
细粒度坐标建图最坏约 10⁸⚠️ 逻辑对但会 MLE/TLE,只适合对拍
只算掉落高度(漏横走)2n❌ 反例即挂(样例得 99997)
05
算法流程图
建 2n 个端点状态 + 一次 Dijkstra
开始读入 n、s、t 与 n 行 (lᵢ, rᵢ, hᵢ)枚举每块挡板的左右端点在坐标 x 处向下找落点挡板 m(hₘ 是低于 hᵢ 中最高的)连掉落边:(i, side) → (m, 左) 与 (m, 右),权 = (hᵢ − hₘ) + 横走距离连同板边:(i, 左) ↔ (i, 右),权 = rᵢ − lᵢ所有端点都处理完了吗?以 (s, 左端点) 为源跑 Dijkstra,得到 2n 个状态的最短距离ans = min over m:若 m 掉落正好落到 t,取 d[m] + (hₘ − hₜ)s = t 或 ans 有定义吗?是 ✓输出 ans(s = t 时为 0)否 ✗输出 −1结束处理下一个端点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🧱 最少耗时计算器(端点状态 + Dijkstra)

第一行输入 n,第二行输入 s t,随后 n 行每行输入 l r h。程序会求出每块挡板左右端点的最短距离、该端点向下落到的挡板,以及最终答案。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(端点状态 + Dijkstra)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 4e18;            // 距离上限约 2 × 10⁵,long long 存更稳

int n, s, t;
int L[1005], R[1005], H[1005];

// 在坐标 x 处、从高度 hi 向下落,返回落到的挡板编号;0 表示掉出系统
int landOn(int x, int hi) {
    int best = 0, bestH = -1;
    for (int i = 1; i <= n; i++) {
        if (H[i] < hi && L[i] <= x && x <= R[i] && H[i] > bestH) {
            bestH = H[i];
            best = i;                      // 取"低于 hi 中最高"的那块 = 下落时最先碰到
        }
    }
    return best;
}

int main() {
    scanf("%d", &n);
    scanf("%d %d", &s, &t);
    for (int i = 1; i <= n; i++) scanf("%d %d %d", &L[i], &R[i], &H[i]);

    // 状态编号:id(i, 0) = 2i - 2 表示左端点,id(i, 1) = 2i - 1 表示右端点
    int V = 2 * n;
    vector<vector<pair<int, ll> > > g(V);

    for (int i = 1; i <= n; i++) {
        int a = 2 * i - 2, b = 2 * i - 1;
        ll walk = R[i] - L[i];
        g[a].push_back(make_pair(b, walk));      // 同板内左右互通
        g[b].push_back(make_pair(a, walk));

        int m1 = landOn(L[i], H[i]);             // 左端点向外掉落
        if (m1) {
            ll drop = H[i] - H[m1];
            // 落到 m1 的中间位置 L[i],再走到 m1 的左 / 右端点
            g[a].push_back(make_pair(2 * m1 - 2, drop + (L[i] - L[m1])));
            g[a].push_back(make_pair(2 * m1 - 1, drop + (R[m1] - L[i])));
        }

        int m2 = landOn(R[i], H[i]);             // 右端点向外掉落
        if (m2) {
            ll drop = H[i] - H[m2];
            g[b].push_back(make_pair(2 * m2 - 2, drop + (R[i] - L[m2])));
            g[b].push_back(make_pair(2 * m2 - 1, drop + (R[m2] - R[i])));
        }
    }

    // Dijkstra:源点 = 第 s 块挡板的左端点
    vector<ll> dist(V, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    int src = 2 * s - 2;
    dist[src] = 0;
    pq.push(make_pair(0, src));
    while (!pq.empty()) {
        ll d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (d > dist[u]) continue;
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i].first;
            ll w = g[u][i].second;
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    if (s == t) { printf("0\n"); return 0; }     // 起点就在目标挡板的左端点上

    // 最后一步必然是"从某块挡板 m 掉落到 t",枚举 m 取最小
    ll ans = INF;
    for (int i = 1; i <= n; i++) {
        if (dist[2 * i - 2] < INF && landOn(L[i], H[i]) == t)
            ans = min(ans, dist[2 * i - 2] + (ll)(H[i] - H[t]));
        if (dist[2 * i - 1] < INF && landOn(R[i], H[i]) == t)
            ans = min(ans, dist[2 * i - 1] + (ll)(H[i] - H[t]));
    }

    if (ans >= INF) printf("-1\n");
    else            printf("%lld\n", ans);
    return 0;
}
🔑
三个要点:① 掉落边权一定要包含掉落高度 + 落点走到端点的横走距离,这是本题最容易漏的地方;② landOn 要在"低于当前高度的所有挡板"里取最高的一块,而不是随便找一块;③ 统计答案时用dist + (H[i] − H[t]),那个差值就是最后一段掉落的高度。

📖 关键几行怎么看

代码作用为什么这样写
if (H[i] < hi && L[i] <= x && x <= R[i] && H[i] > bestH)找落点低于 hi 中最高、且区间包含 x 的那一块
g[a].push_back(make_pair(2*m1-2, drop + (L[i]-L[m1])));左端掉落边落到 m1 后走到左端点的总代价
g[a].push_back(make_pair(2*m1-1, drop + (R[m1]-L[i])));左端掉落边落到 m1 后走到右端点的总代价
g[a].push_back(make_pair(b, walk));同板横走板内左右端点互通,权为板长
if (s == t) { printf("0\n"); return 0; }起点即终点从 s 左端点出发就在 t 上,耗时 0
landOn(L[i], H[i]) == t统计答案只有"正好落到 t"这个掉落才能作为最后一步
⚠️
五个坑:① 掉落边漏掉横走距离(样例会得 99997);② 用错端点坐标去找落点或算横走(左端掉落必须用 L[i]);③ landOn 取成了"最低"而不是"低于 hi 中最高";④ 忘记 s = t 的特判;⑤ 距离上界用 int 且 INF 设得太小(用 long long + 4e18 最稳)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
3 1
5 6 3
3 5 6
1 4 100000
100001题面样例:3 → 2 → 1,含"落点再横走 1"
3
2 2
5 6 3
3 5 6
1 4 100000
0s = t 特判:起点就在目标板左端点
2
2 1
1 2 10
3 4 5
−1两块挡板水平错开,掉落时下方接不住
2
2 1
1 4 1
2 3 5
4上层板左端点正下方就是下层板:掉落 4
3
3 1
1 10 1
2 8 5
3 7 9
9三层嵌套:9 → 5 掉 4、走 1、再掉 4
3
3 2
1 10 1
2 8 5
3 7 9
4只掉一层就到达目标
1
1 1
1 3 4
0只有一块挡板,s = t
2
1 2
1 5 9
6 8 3
−1目标板在上层且水平不可达
✅
自查清单:① 掉落边加了横走距离吗?② landOn 取的是"最低下方最高"吗?③ s = t 判了吗?④ 不可达输出 −1 了吗?

🚨 易错点清单

⚠️
掉落边漏掉横走距离:样例会从 100001 变成 99997,这是本题第一大坑。
⚠️
落点找错:landOn 必须取"低于当前高度中最高"的一块;取最低会把直接掉到远处的方案算成合法。
⚠️
端点混用:从左端掉落要用 L[i] 找落点并算横走,从右端掉落要用 R[i],不能混。
⚠️
忘记 s = t:起点就在目标挡板上,答案应为 0 而不是 −1。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n² + n log n)
空间复杂度
O(n)
状态数
2n ≤ 2000
n 上限
1000

时间怎么算的?

空间都用在哪?

邻接表存 O(n) 条边、距离数组长度 2n、外加 L / R / H 三个长度 n 的数组,全部是 O(n)。

✅ 难点不在复杂度,而在建模是否等价:把状态压缩到端点、把横走距离折进掉落边权,两步都对,正确性才有保证。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「离散状态 + 掉落边」通用建模模板
// 1) 状态:只取"会改变决策的位置"(本题是每块挡板的两个端点)
//    理由:板内代价 = 距离,板中间停留不会带来新选择

// 2) 找"正下方第一块挡板"
int landOn(int x, int hi) {
    int best = 0, bestH = -1;
    for (int i = 1; i <= n; i++)
        if (H[i] < hi && L[i] <= x && x <= R[i] && H[i] > bestH) {
            bestH = H[i]; best = i;          // 下方最高的那块
        }
    return best;                             // 0 = 掉出系统(不连边)
}

// 3) 掉落边:把"落到板内 → 走到端点"的距离直接打包进权
//    from (i, side) 到 (m, 左/右):
//    w = (h_i - h_m) + 落点 到 m 的端点 的横向距离

// 4) 最后一步专门统计:能掉到 t 的 m,候选 = dist[m] + (h_m - h_t)

// 5) 收尾:s == t -> 0;一个候选都没有 -> -1

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
状态压缩只保留"决策点"(端点),板内用距离折算平台/传送带/管道类几何最短路
找落点扫描在"低于当前高度"的候选中取最高的一块区间覆盖查询(可换线段树 / 树状数组优化到 O(log n))
边权打包把"落点 → 端点"的横走距离并进掉落边任何"进入某结构后再离开"的代价都可以这样折算
最后一步枚举枚举"从哪块掉过来",而不是枚举到达的坐标终点是"区域"而非"点"的最短路题
🌟
思考题:如果把 n 放大到 10⁵,这套做法哪里会先爆?该怎么改?(提示:瓶颈是"每个端点都 O(n) 扫描找落点",即 O(n²) 的建图。可以先把所有挡板按高度排序,再用"区间覆盖 + 线段树/并查集"在 O(n log n) 内求出每个端点的落点;——把"暴力找落点"换成"数据结构加速",是本题最自然的扩展方向。)