把状态压缩成每块挡板的左右端点(共 2n 个点),掉落边带上"落到板内再走到端点"的代价,跑 Dijkstra。
小杨在二维空间中有 n 个水平挡板,并且挡板之间彼此不重叠,其中第 i 个挡板处于水平高度 hᵢ,左右端点分别位于 lᵢ 与 rᵢ。
小杨可以在挡板上左右移动,当小杨移动到右端点时,如果再向右移动会竖直掉落,从而落到下方第一个挡板上,移动到左端点时同理。小杨在挡板上每移动 1 个单位长度会耗费 1 个单位时间,掉落时每掉落 1 个单位高度也会耗费 1 个单位时间。
小杨想知道,从第 s 个挡板上的左端点出发到第 t 个挡板需要耗费的最少时间是多少?
注意:可能无法从第 s 个挡板到达到第 t 个挡板。
第一行一个正整数 n,代表挡板数量。
第二行两个正整数 s, t,含义如题面所示。
之后 n 行,每行三个正整数 lᵢ, rᵢ, hᵢ,代表第 i 个挡板。
输出一个整数代表需要耗费的最少时间;如果无法到达则输出 −1。
| 样例 | 输入 | 输出 |
|---|---|---|
| #1 | 33 15 6 33 5 61 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% 无特殊限制 |
i 块的端点掉下去,落点坐标是那个端点的 x,落到第 m 块上的中间某点,想再往外掉就必须先走到 m 的某个端点。这段横向距离必须算进去,否则会严重低估答案(样例里正是 +1 那一项)x 垂直向下看时,能落到的挡板是唯一确定的,于是"找落点"只是一个简单扫描,不需要处理歧义t 的最后一步必然是"从某块挡板 m 掉落到 t"(或者 s = t)。所以只要枚举每块 m:若从它的左端点掉落正好落到 t,答案候选就是 dist(m, 左) + (hₘ − hₜ);右端点同理。全部取最小值t,输出 −1三块挡板:
| 编号 | 区间 [l, r] | 高度 h | 说明 |
|---|---|---|---|
| 1 | [5, 6] | 3 | 最矮,位于右侧 |
| 2 | [3, 5] | 6 | 中间高度 |
| 3 | [1, 4] | 100000 | 最高,起点所在 |
从第 3 块的左端点 x = 1, h = 100000 出发。题面给出的最优方案是"先向右走到端点,再掉到 2,再掉到 1"。
水平距离 4 − 1 = 3
耗时 3,位置变为 (x = 4, h = 100000)
顺便说明:如果此时向左走,x = 1 处下方没有任何挡板包含 1(挡板 2 是 [3, 5],挡板 1 是 [5, 6]),会直接掉出系统,所以只能往右
累计 3
在 x = 4 处向下看,第一个与之相交的挡板是第 2 块([3, 5],h = 6)
掉落高度 100000 − 6 = 99994
落点为 (x = 4, h = 6),落在挡板 2 的内部
注意落点不是挡板 2 的端点,还得继续走
累计 3 + 99994 = 99997
水平距离 5 − 4 = 1
耗时 1,位置变为 (x = 5, h = 6)
为什么向右?因为 x = 5 下方只有挡板 1([5, 6])能接住,而挡板 1 正是终点
累计 99997 + 1 = 99998
在 x = 5 处向下看,能接住的是第 1 块([5, 6],h = 3)
掉落高度 6 − 3 = 3
落到挡板 1 上即到达终点,不需要再走
✅ 累计 99998 + 3 = 100001
| 段 | 动作 | 代价 | 累计 |
|---|---|---|---|
| 1 | 挡板 3 上:x = 1 → x = 4 | 3 | 3 |
| 2 | x = 4 向右掉落:h = 100000 → h = 6 | 99994 | 99997 |
| 3 | 挡板 2 上:x = 4 → x = 5 | 1 | 99998 |
| 4 | x = 5 向右掉落:h = 6 → h = 3 | 3 | 100001 |
把每块挡板拆成左端点状态与右端点状态,共 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 的中间后往右走到端点 |
对挡板 i 的左端点 x = Lᵢ:在所有 Hₘ < Hᵢ 且 Lₘ ≤ x ≤ Rₘ 的挡板里
取高度最大的那块 m(它就是下落时最先碰到的那块)
如果一块都没有,说明这个方向会掉出系统,不连边
落点唯一("互不重叠"的功劳)
落点坐标是端点的 x(比如 Lᵢ)
走到 m 左端点的距离 = Lᵢ − Lₘ
走到 m 右端点的距离 = Rₘ − Lᵢ
边权 = 掉落高度 (Hᵢ − Hₘ) + 横走距离
✅ 状态里就不用记录"板内位置"了
源点 = (s, 左),dist = 0
跑堆优化 Dijkstra,得到所有 2n 个状态的最短距离
dist 全部就位
若 s = t,答案 0(起点就在目标板左端点)
否则枚举每块 m:若从 m 的左端点掉落正好落到 t,候选值 = dist(m, 左) + (Hₘ − Hₜ)
右端点同理;所有候选取最小
一个候选都没有 → 输出 −1
✅ 得到最少时间或 −1
Rᵢ 去找 m,之后横走距离按 Rᵢ 与 Lₘ / Rₘ 计算,不要混用左端点;③ 统计答案时别忘 s = t,起点就在目标板上,答案是 0。每块挡板只保留左端点、右端点两个状态(2n 个点),掉落边权 = 掉落高度 + 落到板内后走到端点的横走距离
(挡板 i, 坐标 x)都建点,左右走 1 单位连一条权 1 的边,端点上连掉落边
lᵢ, rᵢ ≤ 10⁵、n ≤ 1000,把所有整数坐标都展开最坏是 10⁸ 个状态,内存直接爆掉。但它的正确性很直观,适合写小数据对拍程序。| 方案 | 状态数 | 结论 |
|---|---|---|
| 端点状态 + Dijkstra | 2n ≤ 2000 | ✅ 正确,本题正解 |
| 细粒度坐标建图 | 最坏约 10⁸ | ⚠️ 逻辑对但会 MLE/TLE,只适合对拍 |
| 只算掉落高度(漏横走) | 2n | ❌ 反例即挂(样例得 99997) |
第一行输入 n,第二行输入 s t,随后 n 行每行输入 l r h。程序会求出每块挡板左右端点的最短距离、该端点向下落到的挡板,以及最终答案。
点按钮开始 →
#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"这个掉落才能作为最后一步 |
L[i]);③ landOn 取成了"最低"而不是"低于 hi 中最高";④ 忘记 s = t 的特判;⑤ 距离上界用 int 且 INF 设得太小(用 long long + 4e18 最稳)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 100001 | 题面样例:3 → 2 → 1,含"落点再横走 1" |
3 | 0 | s = t 特判:起点就在目标板左端点 |
2 | −1 | 两块挡板水平错开,掉落时下方接不住 |
2 | 4 | 上层板左端点正下方就是下层板:掉落 4 |
3 | 9 | 三层嵌套:9 → 5 掉 4、走 1、再掉 4 |
3 | 4 | 只掉一层就到达目标 |
1 | 0 | 只有一块挡板,s = t |
2 | −1 | 目标板在上层且水平不可达 |
landOn 取的是"最低下方最高"吗?③ s = t 判了吗?④ 不可达输出 −1 了吗?landOn 必须取"低于当前高度中最高"的一块;取最低会把直接掉到远处的方案算成合法。L[i] 找落点并算横走,从右端掉落要用 R[i],不能混。2n 个端点,每个端点用一次 O(n) 扫描找落点,合计 O(n²) ≤ 10⁶2n、边数 O(n),堆优化 O(n log n)邻接表存 O(n) 条边、距离数组长度 2n、外加 L / R / H 三个长度 n 的数组,全部是 O(n)。
✅ 难点不在复杂度,而在建模是否等价:把状态压缩到端点、把横走距离折进掉落边权,两步都对,正确性才有保证。
// 「离散状态 + 掉落边」通用建模模板 // 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) 内求出每个端点的落点;——把"暴力找落点"换成"数据结构加速",是本题最自然的扩展方向。)