A32169. 空间跳跃题面描述小杨在二维空间中有n个水平挡板，并且挡板之间彼此不重叠，其中第i个挡板处于水平高度h，左右端点分别位 于 li 与 ri 。小杨可以在挡板上左右移动，当小杨移动到右端点时，如果再向右移动会竖直掉落，从而落到下方第一个挡板上， 移动到左端点时同理。小杨在挡板上每移动1个单位长度会耗费1个单位时间，掉落时每掉落1个单位高度也会耗费1单位时间。小杨想知道，从第s个挡板上的左端点出发到第…
填空题
困难
知识点
题目描述
空间跳跃
题面描述
小杨在二维空间中有n个水平挡板，并且挡板之间彼此不重叠，其中第i个挡板处于水平高度h，左右端点分别位 于 li 与 ri 。
小杨可以在挡板上左右移动，当小杨移动到右端点时，如果再向右移动会竖直掉落，从而落到下方第一个挡板上， 移动到左端点时同理。小杨在挡板上每移动1个单位长度会耗费1个单位时间，掉落时每掉落1个单位高度也会耗费1单位时间。
小杨想知道，从第s个挡板上的左端点出发到第t个挡板需要耗费的最少时间是多少？
注意：可能无法从第s个挡板到达到第t个挡板。
输入格式
第一行包含一个正整数n，代表挡板数量。
第二行包含两个正整数s，t，含义如题面所示。
之后n行，每行包含三个正整数 li ri hi 代表第i个挡板的左右端点位置与高度。
输出格式
输出一个整数代表需要耗费的最少时间，如果无法到达则输出-1。
样例1
输入
3
31
563
356
14100000
输出
100001
样例范围
耗费时间最少的移动方案为，从第3个挡板左端点移动到右端点，耗费3个单位时间，然后向右移动掉落到第2个 挡板上，耗费100000-6=9994个单位时间，之后再向右移动1个单位长度，耗费1个单位时间，最后向右移动 掉落到第1个挡板上，耗费3个单位时间。共耗费3+9994+1+3=100001个单位时间。
数据范围
参考答案
#include<bits/stdc++.h>
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>(const node& a) const {
return dis > a.dis;
}
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;
int cnt;
void dijkstra(int s) {
for(int i=1; i<=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] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push(node(dis[v], v));
}
}
}
}
map<pair<int,int>,int> mp;
vector<int> es[2010];
int l[maxn],r[maxn],h[maxn];
int main() {
int n;
cin>>n;
int s,t;
cin>>s>>t;
for(int i=1; i<=n; i++) {
cin>>l[i]>>r[i]>>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<=n; i++) {
int hh = -1,idx = i;
for(int j=1; j<=n; j++) {
if(i==j)continue;
if(l[j]<=l[i]&&l[i]<=r[j]&&h[j]<=h[i]) {
if(h[j]>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<=n; j++) {
if(i==j)continue;
if(l[j]<=r[i]&&r[i]<=r[j]&&h[j]<=h[i]) {
if(h[j]>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<<ans<<"\n";
else cout<<"-1\n";
}
上一题
下一题