题解：P10726 [GESP202406 八级] 空间跳跃

· · 题解

有人在考场上两分钟想到建边跑最短路，但是两度看错数据范围，并尝试使用树状数组来维护区间赋值，痛失 S 组免初赛资格，我不说是谁。

解析

读完题目，我们发现，在挡板上移动与垂直掉落的本质是一样的，都是消耗 1 单位时间，移动 1 单位长度。

所以我们可以考虑建边，具体地，对于每个挡板的左端点，向右端点连一条边权为挡板长度的双向边，代表在挡板上移动。

对于每个挡板的端点 u，尝试从该端点垂直向下连一条单向边，连到位于该端点正下方第一个挡板上，我们在这里新开一个点，边权为两挡板高度差，代表垂直下落，下方没有挡板则不连。

然后，从新开的这个点出发，往所在挡板的左右端点分别连单向边，边权为该点到左右端点的距离，即 u 到该挡板左右端点的水平距离，代表垂直下落之后在挡板上移动。

如何给结点编号？我的做法是，令第 i 个挡板的左端点的编号为 2i - 1，右端点编号为 2i，这样就有了 2n 个点，向下连边的时候再一个一个加点。

可能有点抽象，放个图：

可以发现，除了起点挡板，其余挡板不需要用双向边来连接左右端点，不过这不是必要的优化。

建完边，从 2s-1 （起点挡板的左端点）开始跑单源最短路即可，我采用的是不加优化的 Dijkstra，答案为在挡板 t 上的所有点的 dis 最小值。

暴力找到一个挡板的端点正下方的第一个挡板，复杂度是 O(n) 的，找 n 个挡板，复杂度为 O(n^2)，暴力 Dijkstra 的复杂度为 O(n^2)，故总复杂度为 O(n^2)，足以通过此题。

代码


#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N = 1e3 + 5, mod = 10007;
int cnt;
struct B{
    int l,r,h;//存储挡板的信息
}b[N];
vector<pii> g[N<<2];
bool vis[N<<2];
ll dis[N<<2];
int n,s,t;
void dij(){
    memset(dis,127,sizeof(dis));
    dis[s * 2 - 1] = 0;
    while(1){
        int u = 0;
        for(int i=1;i<=cnt;i++){
            if(!vis[i] && dis[i] < dis[u]){
                u = i;
            }
        }
        if(!u) break;
        vis[u] = true;
        for(pii p : g[u]){
            int v = p.first,w = p.second;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
            }
        }
    } 
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    vector<int> fin;//在挡板 t 上的点
    cin>>n>>s>>t;
    fin.push_back(t * 2 - 1),fin.push_back(t * 2);//
    for(int i=1;i<=n;i++){
        cin>>b[i].l>>b[i].r>>b[i].h;
        cnt += 2;
        int lpos = i * 2 - 1,rpos = i * 2;
        g[lpos].push_back(mp(rpos,b[i].r - b[i].l));
        g[rpos].push_back(mp(lpos,b[i].r - b[i].l));
    }
    for(int i=1;i<=n;i++){
        int lb = 0,rb = 0;//左右端点向下找到的第一个挡板（比当前挡板低的最高的挡板）
        int mxlh = 0,mxrh = 0;//找到的挡板的高度
        for(int j=1;j<=n;j++){
            if(b[j].h < b[i].h && b[j].h > mxlh && b[i].l <= b[j].r && b[i].l >= b[j].l){
                mxlh = b[j].h;
                lb = j;
            }
            if(b[j].h < b[i].h && b[j].h > mxrh && b[i].r <= b[j].r && b[i].r >= b[j].l){
                mxrh = b[j].h;
                rb = j;
            }
        }
        int lpos = i * 2 - 1,rpos = i * 2;
        int lhcha = b[i].h - mxlh,rhcha = b[i].h - mxrh;//高度差
        if(lb){
            cnt++;
            g[lpos].push_back(mp(cnt,lhcha));
            g[cnt].push_back(mp(lb * 2 - 1,b[i].l - b[lb].l));
            g[cnt].push_back(mp(lb * 2,b[lb].r - b[i].l));
            if(lb == t){
                fin.push_back(cnt);
            }
        }

        if(rb){
            cnt++;
            g[rpos].push_back(mp(cnt,rhcha));
            g[cnt].push_back(mp(rb * 2 - 1,b[i].r - b[rb].l));
            g[cnt].push_back(mp(rb * 2,b[rb].r - b[i].r));
            if(rb == t){
                fin.push_back(cnt);
            }
        }

    }
    dij();
    ll res = 9e18;
    for(int i : fin){
        res = min(res,dis[i]);
    }
    cout<<(res == 9e18 ? -1 : res);
    return 0;
}