[GESP202406 八级] 空间跳跃

GESP编程共123题，本题是整站第1425题，已经有人完成了本题，加油！

题目描述

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

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

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

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

输入格式

第一行包含一个正整数 n，代表挡板数量。

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

之后 n 行，每行包含三个正整数 li,ri,hi，代表第 i 个挡板的左右端点位置与高度。

输出格式

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

输入输出样例

输入 #1

输出 #1

说明/提示

样例解释

耗费时间最少的移动方案为，从第 3 个挡板左端点移动到右端点，耗费 3 个单位时间，然后向右移动掉落到第 2 个挡板上，耗费 100000−6=99994 个单位时间，之后再向右移动 1 个单位长度，耗费 1 个单位时间，最后向右移动掉落到第 1 个挡板上，耗费 3 个单位时间。共耗费 100001 个单位时间。

数据范围

子任务编号	数据点占比	n	特殊条件
1	20%	≤1000	li=1
2	40%	≤1000	li=i,ri=i+1
3	40%	≤1000

对于全部数据，保证有 1≤n≤1000，1≤li≤ri≤10^5，1≤hi≤10^5。

真题解析

【题目大意】

在二维空间里描述每个挡板有3个信息，左右端点和高度。根据测试样例，画出3个挡板的信息。1号挡板不一定在最上面，根据数据判断。3号挡板从1移到4，不能直接掉到1号挡板。先掉到2号挡板，再掉到1号挡板。

【考纲知识点】

建图知识，最短路径

【解题思路】

发现n的数据范围是1000，求的是从1个挡板到另外1个挡板。注意，掉到目标挡板中的某个位置即可。同时1个挡板左端到右端或者右端到左端算距离，其他挡板的2个端点只要能垂直相交到下一个挡板（中间没有其他挡板阻碍），也算相连。将这些端点和相交点看成结点，相连看成边，整个结构就成为一张图的结构。起点是固定的，终点也是固定的（只要是目标挡板的某个点即可），求的就是最短路径。数据都是正整数，可以用dijkstra算法实现。

难点1在于建图。一个挡板左右算2个结点，要连边；一个挡板的左右两端能够垂直到其他挡板，中间不能有间隔，要连边。

难度2就是dijkstra算法的完成。按照优先队列的模板完成即可。

参考程序

本站题目仅供学习，GESP版权归CCF所有，如有侵权请联系删除。站长陈老师QQ及微信:208234。