题解：B4208 [常州市赛 2021] 移动

· · 题解

P14726 [ICPC 2022 Seoul R] Forbidden Turns

题目传送门

前置知识

题目大意

在一个学校里，学生可以在每一层左右移动，也可以在有楼梯的地方上下移动。

题目会让你求从一个地方到另一个地方的时间。

思路

考虑 Floyd 求梯子之间的距离，它可以求出任意两个梯子间的距离。

询问时，求的就是起点能最快到达的那个楼梯和终点能最快到达的楼梯之间的 Floyd 最小距离。

复杂度证明

注意到 1\le k\le300，最多有 300 个梯子，Floyd 算法为 O(k^3)，其余算法均不是瓶颈，所以该方法不会超时。

代码

请自行写完代码后对拍。

另外，该代码无防抄袭。 :::success[AC 代码]

#include<bits/stdc++.h>
using namespace std;

const int N=305;

struct node{
    long long x,y,z;
}h[N];

long long f[N][N];
vector<int>v1,v2;
long long n,m,k;

inline void Floyd(){
    for(int k1=1;k1<=k;k1++){
        for(int x=1;x<=k;x++){
            for(int y=1;y<=k;y++){
                f[x][y]=min(f[x][y],f[x][k1]+f[k1][y]);
            }
        }
    }
}

int main(){
    memset(f,0x3f,sizeof f);
    scanf("%lld%lld",&n,&m);
    scanf("%lld",&k);
    for(int i=1;i<=k;i++) f[i][i]=0;
    for(int i=1;i<=k;i++){
        long long x,y,z;
        scanf("%lld%lld%lld",&h[i].x,&h[i].y,&h[i].z);
        if(h[i].y>h[i].z) swap(h[i].y,h[i].z);
        x=h[i].x;y=h[i].y;z=h[i].z;
        for(int j=1;j<i;j++){
            if(y<=h[j].z&&h[j].y<=z){
                f[i][j]=abs(h[i].x-h[j].x);
                f[j][i]=abs(h[i].x-h[j].x);
            }
        }
    }
    Floyd();
    long long Q,sx,sy,tx,ty;
    scanf("%lld",&Q);
    while(Q--){
        v1.clear();
        v2.clear();
        scanf("%lld%lld%lld%lld",&sx,&sy,&tx,&ty);
        if(sy==ty){
            printf("%lld\n",abs(sx-tx));
            continue;
        }
        long long res=1e18;
        for(int i=1;i<=k;i++){
            if(h[i].y<=sy&&sy<=h[i].z){
                v1.push_back(i);
            }
        }

        for(int i=1;i<=k;i++){
            if(h[i].y<=ty&&ty<=h[i].z){
                v2.push_back(i);
            }
        }

        for(int i=0;i<v1.size();i++){
            for(int j=0;j<v2.size();j++){
                if(f[v1[i]][v2[j]]==0x3f3f3f3f3f3f3f3f) continue;
                res=min(f[v1[i]][v2[j]]+abs(h[v1[i]].x-sx)+abs(h[v2[j]].x-tx),res);
            }
        }
        if(res>=1e18/2) printf("-1\n");
        else printf("%lld\n",res+abs(sy-ty));
    }
    return 0;
}

::: 后记

笔者在想该代码怎么写时想的最久的一点是入手的那一下，后来观察到了 1\le k\le300 才恍然大悟。