简答题 偏难
#21051

空间跳跃 题面描述 小杨在二维空间中有n个水平挡板,并且挡板之间彼此不重叠,其中第i个挡板处于水平高度h i ,左右端点分别位于l i 与 r i 。 小杨可以…

空间跳跃

题面描述

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

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

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

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

输入格式

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

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

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

输出格式

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


输入样例

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

输出样例

100001

样例范围

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

数据范围

对于全部数据,保证有1≤n≤1000,1≤li≤ri≤105,1≤hi≤105。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int maxn = 1e4+10; struct edge { int v, w; edge() { } edge(int vv,int ww) { v=vv; w=ww; } }; struct node { int dis, u; node () { } node (int diss,int uu) { dis=diss; u=uu; } bool operator&gt;(const node&amp; a) const { return dis &gt; a.dis; } }; vector&lt;edge&gt; e[maxn]; int dis[maxn], vis[maxn]; priority_queue&lt;node, vector&lt;node&gt;, greater&lt;node&gt; &gt; q; int cnt; void dijkstra(int s) { for (int i=1;i&lt;=cnt;i++)dis[i]=INT_MAX; dis[s] = 0; q.push(node(0, s)); while (!q.empty()) { int u = q.top().u; q.pop(); if (vis[u]) continue; vis[u] = 1; for (auto ed : e[u]) { int v = ed.v, w = ed.w; if (dis[v] &gt; dis[u] + w) { dis[v] = dis[u] + w; q.push(node(dis[v], v)); } } } } map&lt;pair&lt;int,int&gt;,int&gt; mp; vector&lt;int&gt; es[2010]; int l[maxn],r[maxn],h[maxn]; int main() { int n; cin&gt;&gt;n; int s,t; cin&gt;&gt;s&gt;&gt;t; for (int i=1;i&lt;=n;i++) { cin&gt;&gt;l[i]&gt;&gt;r[i]&gt;&gt;h[i]; mp[make_pair(l[i],h[i])]=i; mp[make_pair(r[i],h[i])]=n+i; es[i].push_back(i); es[i].push_back(n+i); e[i].push_back(edge(n+i,r[i]-l[i])); e[n+i].push_back(edge(i,r[i]-l[i])); } cnt=2*n+1; for (int i=1;i&lt;=n;i++) { int hh = -1,idx = i; for (int j=1;j&lt;=n;j++) { if(i==j)continue; if(l[j]&lt;=l[i]&amp;&amp;l[i]&lt;=r[j]&amp;&amp;h[j]&lt;=h[i]) { if(h[j]&gt;hh) { hh=h[j]; idx=j; } } } if(hh!=-1) { if(!mp[make_pair(l[i],hh)]) { mp[make_pair(l[i],hh)]=cnt++; } int v = mp[make_pair(l[i],hh)]; e[i].push_back(edge(v,h[i]-hh)); e[idx].push_back(edge(v,abs(l[i]-l[idx]))); e[n+idx].push_back(edge(v,abs(l[i]-r[idx]))); e[v].push_back(edge(idx,abs(l[i]-l[idx]))); e[v].push_back(edge(n+idx,abs(l[i]-r[idx]))); es[idx].push_back(v); } hh = -1,idx = i; for (int j=1;j&lt;=n;j++) { if(i==j)continue; if(l[j]&lt;=r[i]&amp;&amp;r[i]&lt;=r[j]&amp;&amp;h[j]&lt;=h[i]) { if(h[j]&gt;hh) { hh=h[j]; idx=j; } } } if(hh!=-1) { if(!mp[make_pair(r[i],hh)]) { mp[make_pair(r[i],hh)]=cnt++; } int v = mp[make_pair(r[i],hh)]; e[n+i].push_back(edge(v,h[i]-hh)); e[idx].push_back(edge(v,abs(r[i]-l[idx]))); e[n+idx].push_back(edge(v,abs(r[i]-r[idx]))); e[v].push_back(edge(idx,abs(r[i]-l[idx]))); e[v].push_back(edge(n+idx,abs(r[i]-r[idx]))); es[idx].push_back(v); } } dijkstra(s); int ans = INT_MAX; for (auto i:es[t]) { ans=min(ans,dis[i]); } if(ans!=INT_MAX)cout&lt;&lt;ans&lt;&lt;"\n"; else cout&lt;&lt;"-1\n"; }</pre>
解析

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

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

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