{"problem":{"name":"[GESP202406 八级] 空间跳跃","description":{"content":"小杨在二维空间中有 $n$ 个水平挡板，并且挡板之间彼此不重叠，其中第 $i$ 个挡板处于水平高度 $h_i$，左右端点分别位于 $l_i$ 与 $r_i$。 小杨可以在挡板上左右移动，当小杨移动到右端点时，如果再向右移动会竖直掉落，从而落到下方第一个挡板上，移动到左端点时同理。小杨在挡板上每移动 $1$ 个单位长度会耗费 $1$ 个单位时间，掉落时每掉落 $1$ 个单位高度也会耗费 $1$ 个","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":512000},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10726"},"statements":[{"statement_type":"Markdown","content":"小杨在二维空间中有 $n$ 个水平挡板，并且挡板之间彼此不重叠，其中第 $i$ 个挡板处于水平高度 $h_i$，左右端点分别位于 $l_i$ 与 $r_i$。\n\n小杨可以在挡板上左右移动，当小杨移动到右端点时，如果再向右移动会竖直掉落，从而落到下方第一个挡板上，移动到左端点时同理。小杨在挡板上每移动 $1$ 个单位长度会耗费 $1$ 个单位时间，掉落时每掉落 $1$ 个单位高度也会耗费 $1$ 个单位时间。\n\n小杨想知道，从第 $s$ 个挡板上的左端点出发到第 $t$ 个挡板需要耗费的最少时间是多少？\n\n注意：可能无法从第 $s$ 个挡板到达到第 $t$ 个挡板。\n\n## Input\n\n第一行包含一个正整数 $n$，代表挡板数量。\n\n第二行包含两个正整数 $s,t$，含义如题面所示。\n\n之后 $n$ 行，每行包含三个正整数 $l_i,r_i,h_i$，代表第 $i$ 个挡板的左右端点位置与高度。\n\n## Output\n\n输出一个整数代表需要耗费的最少时间，如果无法到达则输出 $-1$。\n\n[samples]\n\n## Background\n\n对应的选择、判断题：<https://ti.luogu.com.cn/problemset/1156>\n\n## Note\n\n### 样例解释\n\n耗费时间最少的移动方案为，从第 $3$ 个挡板左端点移动到右端点，耗费 $3$ 个单位时间，然后向右移动掉落到第 $2$ 个挡板上，耗费 $100000-6=99994$ 个单位时间，之后再向右移动 $1$ 个单位长度，耗费 $1$ 个单位时间，最后向右移动掉落到第 $1$ 个挡板上，耗费 $3$ 个单位时间。共耗费 $100001$ 个单位时间。\n\n### 数据范围\n\n子任务编号|数据点占比|$n$|特殊条件\n:-:|:-:|:-:|:-:\n$1$|$20\\%$|$\\leq 1000$|$l_i=1$\n$2$|$40\\%$|$\\leq 1000$|$l_i=i,r_i=i+1$\n$3$|$40\\%$|$\\leq 1000$|\n\n对于全部数据，保证有 $1\\leq n\\leq 1000$，$1\\leq l_i\\leq r_i\\leq 10^5$，$1\\leq h_i\\leq 10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10726","tags":["动态规划 DP","2024","最短路","GESP"],"sample_group":[["3\n3 1\n5 6 3\n3 5 6\n1 4 100000","100001"]],"created_at":"2026-03-03 11:09:25"}}