奇怪的电梯题解

· · 题解

这题其实可以使用最短路解决。
对于每一个点 i 与这个点对应的 k_i，我们可以进行如下处理。

最后使用最短路算法算出从 A 点到 B 点的最短路就好了。
这份代码使用邻接矩阵存边以及弗洛伊德算法求最短路。

#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int f[N][N];//最短路数组，f[i][j] 代表从 i 层到 j 层最小按按钮次数
int main(){
    int n, a, b;
    cin >> n >> a >> b;
    memset(f, INF, sizeof(f));//初始化路径数组为无穷大
    for(int i = 1 ; i <= n ; i++){
        int k;
        cin >> k;
        int u = i,up = u + k, down = u - k;//up为上升可以到达的楼层，down为下降可以到达的楼层
        if(up <= n){//如果这个楼层是合法的
            f[u][up] = 1;//从楼层 i 向楼层 i + k 连一条权值为 1 的边
        }
        if(down >= 1){//同上
            f[u][down] = 1;//从楼层 i 向楼层 i - k 连一条权值为 1 的边
        }
    }
    for(int i = 1 ; i <= n ; i++)   f[i][i] = 0;//同一楼层不用坐电梯
    for(int k = 1 ; k <= n ; k++){//弗洛伊德算法
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= n ; j++){
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
    if(f[a][b] == INF)  cout << -1 << endl;//无法到达
    else    cout << f[a][b] << endl;
    return 0;
}