题目背景对应的选择、判断题试题 - GESP 202406 C 八级 - 洛谷有题题目描述小杨在二维空间中有 n 个水平挡板并且挡板之间彼此不重叠其中第 i 个挡板处于水平高度 hi​左右端点分别位于 li​ 与 ri​。小杨可以在挡板上左右移动当小杨移动到右端点时如果再向右移动会竖直掉落从而落到下方第一个挡板上移动到左端点时同理。小杨在挡板上每移动 1 个单位长度会耗费 1 个单位时间掉落时每掉落 1 个单位高度也会耗费 1 个单位时间。小杨想知道从第 s 个挡板上的左端点出发到第 t 个挡板需要耗费的最少时间是多少注意可能无法从第 s 个挡板到达到第 t 个挡板。输入格式第一行包含一个正整数 n代表挡板数量。第二行包含两个正整数 s,t含义如题面所示。之后 n 行每行包含三个正整数 li​,ri​,hi​代表第 i 个挡板的左右端点位置与高度。输出格式输出一个整数代表需要耗费的最少时间如果无法到达则输出 −1。输入输出样例输入 #1复制3 3 1 5 6 3 3 5 6 1 4 100000输出 #1复制100001说明/提示样例解释耗费时间最少的移动方案为从第 3 个挡板左端点移动到右端点耗费 3 个单位时间然后向右移动掉落到第 2 个挡板上耗费 100000−699994 个单位时间之后再向右移动 1 个单位长度耗费 1 个单位时间最后向右移动掉落到第 1 个挡板上耗费 3 个单位时间。共耗费 100001 个单位时间。数据范围子任务编号数据点占比n特殊条件120%≤1000li​1240%≤1000li​i,ri​i1340%≤1000对于全部数据保证有 1≤n≤10001≤li​≤ri​≤1051≤hi​≤105。代码实现#include bits/stdc.h using namespace std; const int MAXN 1005; const long long INF 1e18; struct Board { int l, r, h; } b[MAXN]; vectorpairint, int G[2005]; long long dis[2005]; bool vis[2005]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, s, t; cin n s t; for(int i 1; i n; i) { cin b[i].l b[i].r b[i].h; } for(int i 1; i n; i) { int L 2*i; int R 2*i1; int w b[i].r - b[i].l; G[L].emplace_back(R, w); G[R].emplace_back(L, w); } long long ans INF; for(int u 1; u n; u) { int hu b[u].h; int xu b[u].r; int bestv -1; int minh -1; for(int v 1; v n; v) { if(u v) continue; int hv b[v].h; if(hv hu b[v].l xu xu b[v].r) { if(minh -1 || hv minh) { minh hv; bestv v; } } } if(bestv ! -1) { int v bestv; int cost hu - b[v].h; if(v t) { G[2*u1].emplace_back(0, cost); } else { G[2*u1].emplace_back(2*v, cost (xu - b[v].l)); G[2*u1].emplace_back(2*v1, cost (b[v].r - xu)); } } } for(int u 1; u n; u) { int hu b[u].h; int xu b[u].l; int bestv -1; int minh -1; for(int v 1; v n; v) { if(u v) continue; int hv b[v].h; if(hv hu b[v].l xu xu b[v].r) { if(minh -1 || hv minh) { minh hv; bestv v; } } } if(bestv ! -1) { int v bestv; int cost hu - b[v].h; if(v t) { G[2*u].emplace_back(0, cost); } else { G[2*u].emplace_back(2*v, cost (xu - b[v].l)); G[2*u].emplace_back(2*v1, cost (b[v].r - xu)); } } } fill(dis, dis2005, INF); priority_queuepairlong long, int, vectorpairlong long, int, greater pq; int start 2*s; dis[start] 0; pq.emplace(0, start); while(!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if(vis[u]) continue; vis[u] true; for(auto [v,w]:G[u]) { if(dis[v] d w) { dis[v] d w; pq.emplace(dis[v], v); } } } ans min({dis[0], dis[2*t], dis[2*t1]}); if(ans INF) cout -1 endl; else cout ans endl; return 0; }