空间跳跃

题目描述

⼩杨在⼆维空间中有 个⽔平挡板，并且挡板之间彼此不重叠，其中第 个挡板处于⽔平⾼度 ，左右端点分别位 于 与 。 ⼩杨可以在挡板上左右移动，当⼩杨移动到右端点时，如果再向右移动会竖直掉落，从⽽落到下⽅第⼀个挡板上， 移动到左端点时同理。⼩杨在挡板上每移动 个单位长度会耗费 个单位时间，掉落时每掉落 个单位⾼度也会耗 费 个单位时间。 ⼩杨想知道，从第 个挡板上的左端点出发到第 个挡板需要耗费的最少时间是多少？ 注意：可能⽆法从第 个挡板到达到第 个挡板。

输入格式

第⼀⾏包含⼀个正整数 ，代表挡板数量。 第⼆⾏包含两个正整数 ，含义如题⾯所⽰。 之后 ⾏，每⾏包含三个正整数 ，代表第 个挡板的左右端点位置与⾼度。

输出格式

输出⼀个整数代表需要耗费的最少时间，如果⽆法到达则输出 。 3.2.4 样例1 1 3 2 3 1 3 5 6 3 4 3 5 6 5 1 4 100000 1 100001 3.2.5 样例范围 耗费时间最少的移动⽅案为，从第 个挡板左端点移动到右端点，耗费 个单位时间，然后向右移动掉落到第 个 挡板上，耗费 个单位时间，之后再向右移动 个单位长度，耗费 个单位时间，最后向右移动 掉落到第 个挡板上，耗费 个单位时间。共耗费 个单位时间。 3.2.6 数据范围 子任务编号 数据点占比 特殊条件 1 20% 2 40% 3 40% 对于全部数据，保证有 ， ， 。 3.2.7 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 1e4+10; 5 6 struct edge { 7 int v, w; 8 9 edge(){} 10 edge(int vv,int ww){ 11 v=vv;w=ww; 12 } 13 }; 14 15 struct node { 16 int dis, u; 17 node (){} 18 node (int diss,int uu){dis=diss;u=uu;} 19 bool operator>(const node& a) const { return dis > a.dis; } 20 }; 21 22 vector e[maxn]; 23 int dis[maxn], vis[maxn]; 24 priority_queue<node, vector, greater > q; 25 int cnt; 26 void dijkstra(int s) { 27 for(int i=1;i<=cnt;i++)dis[i]=INT_MAX; 28 dis[s] = 0; 29 q.push(node(0, s)); 30 while (!q.empty()) { 31 int u = q.top().u; 32 q.pop(); 33 if (vis[u]) continue; 34 vis[u] = 1; 35 for (auto ed : e[u]) { 36 int v = ed.v, w = ed.w; 37 if (dis[v] > dis[u] + w) { 38 dis[v] = dis[u] + w; 39 q.push(node(dis[v], v)); 40 } 41 } 42 } 43 } 44 45 map<pair<int,int>,int> mp; 46 vector es[2010]; 47 int l[maxn],r[maxn],h[maxn]; 48 int main(){ 49 int n; 50 cin>>n; 51 int s,t; 52 cin>>s>>t; 53 for(int i=1;i<=n;i++){ 54 cin>>l[i]>>r[i]>>h[i]; 55 mp[make_pair(l[i],h[i])]=i; 56 mp[make_pair(r[i],h[i])]=n+i; 57 es[i].push_back(i); 58 es[i].push_back(n+i); 59 e[i].push_back(edge(n+i,r[i]-l[i])); 60 e[n+i].push_back(edge(i,r[i]-l[i])); 61 } 62 cnt=2*n+1; 63 for(int i=1;i<=n;i++){ 64 int hh = -1,idx = i; 65 for(int j=1;j<=n;j++){ 66 if(ij)continue; 67 if(l[j]<=l[i]&&l[i]<=r[j]&&h[j]<=h[i]){ 68 if(h[j]>hh){ 69 hh=h[j]; 70 idx=j; 71 } 72 } 73 } 74 if(hh!=-1){ 75 if(!mp[make_pair(l[i],hh)]){ 76 mp[make_pair(l[i],hh)]=cnt++; 77 } 78 int v = mp[make_pair(l[i],hh)]; 79 e[i].push_back(edge(v,h[i]-hh)); 80 e[idx].push_back(edge(v,abs(l[i]-l[idx]))); 81 e[n+idx].push_back(edge(v,abs(l[i]-r[idx]))); 82 e[v].push_back(edge(idx,abs(l[i]-l[idx]))); 83 e[v].push_back(edge(n+idx,abs(l[i]-r[idx]))); 84 es[idx].push_back(v); 85 } 86 hh = -1,idx = i; 87 for(int j=1;j<=n;j++){ 88 if(ij)continue; 89 if(l[j]<=r[i]&&r[i]<=r[j]&&h[j]<=h[i]){ 90 if(h[j]>hh){ 91 hh=h[j]; 92 idx=j; 93 } 94 } 95 } 96 97 if(hh!=-1){ 98 if(!mp[make_pair(r[i],hh)]){ 99 mp[make_pair(r[i],hh)]=cnt++; 100 } 101 int v = mp[make_pair(r[i],hh)]; 102 e[n+i].push_back(edge(v,h[i]-hh)); 103 e[idx].push_back(edge(v,abs(r[i]-l[idx]))); 104 e[n+idx].push_back(edge(v,abs(r[i]-r[idx]))); 105 e[v].push_back(edge(idx,abs(r[i]-l[idx]))); 106 e[v].push_back(edge(n+idx,abs(r[i]-r[idx]))); 107 es[idx].push_back(v); 108 } 109 } 110 dijkstra(s); 111 int ans = INT_MAX; 112 for(auto i:es[t]){ 113 ans=min(ans,dis[i]); 114 } 115 if(ans!=INT_MAX)cout<<ans<<"\n"; 116 else cout<<"-1\n"; 117 118 }

样例输入 #1

1 3
2 3 1
3 5 6 3
4 3 5 6
5 1 4 100000
1 100001
3.2.5 样例范围
耗费时间最少的移动⽅案为，从第 个挡板左端点移动到右端点，耗费 个单位时间，然后向右移动掉落到第 个
挡板上，耗费 个单位时间，之后再向右移动 个单位长度，耗费 个单位时间，最后向右移动
掉落到第 个挡板上，耗费 个单位时间。共耗费 个单位时间。

样例输出 #1

数据范围

子任务编号 数据点占比 特殊条件 1 20% 2 40% 3 40% 对于全部数据，保证有 ， ， 。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。