题目背景

2024 年 6 月 GESP C++ 八级编程第 2 题

题目描述

二维平面中有 $n$ 个互不重叠的水平挡板。第 $i$ 个挡板高度为 $h_i$，左右端点横坐标分别为 $l_i,r_i$。小杨可在挡板上左右移动，每移动 $1$ 个单位长度耗时 $1$；从端点继续向外会竖直下落，落到下方第一个挡板上，每下落 $1$ 个单位高度耗时 $1$。

小杨从第 $s$ 个挡板的左端点出发，想到达第 $t$ 个挡板。求最少耗时；若无法到达，输出 $-1$。

输入格式

第一行输入正整数 $n$。 第二行输入两个正整数 $s,t$。 接下来 $n$ 行，每行输入三个正整数 $l_i,r_i,h_i$，表示一个挡板。

输出格式

输出一行一个整数，表示最少耗时；若无法到达，输出 -1。

3
3 1
5 6 3
3 5 6
1 4 100000

100001

数据范围与提示

• $1 \le n\le 10^5$。
• $1 \le l_i<r_i \le 10^9$，$1 \le h_i \le 10^9$。
• 挡板之间互不重叠；部分数据满足 $n \le 1000$ 或特殊挡板形态。

来源

GESP 2024 年 06 月 C++ 八级 T2