题解：P10948 升降梯上

zhuohongyuan · 2025-08-06 10:54:14 · 题解

题解区都是 bfs 和 dij 的，没人写 spfa，那我就来写个 spfa 的题解。

题意

你需要从第 1 层到第 n 层，有 m 种方式，每种方式上升 c_i 层（c_i 可能为负数）。从第 i 种方式切换到第 j 种方式要 |i - j| 的代价，移动一层要 2 的代价，求最小代价。

思路

明显是一道最短路图论题，只不过把 1 维的拓展到 2 维的而已。

边权非负，数据小，用 spfa 跑最短路也可以。

最重要的就是转移方程的改变。

还有边界的特判（不要跳着跳着跳出 1 或 n 了）。

代码

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

const int maxn = 1000 + 5;
const int maxm = 20 + 5;

int n, m, u;
int dis[maxn][maxm], c[maxm], vis[maxn][maxm];

void spfa(){
    memset(dis, 0x3f, sizeof(dis));
    queue<pair<int, int>> q;
    q.push(make_pair(1, u));
    dis[1][u] = 0;
    vis[1][u] = 1;
    while (!q.empty()){
        pair<int, int> tmp = q.front();
        vis[tmp.first][tmp.second] = 0;
        q.pop();
        for (int k = 1; k <= m; ++k){
            if (tmp.first + c[k] > 0 && tmp.first + c[k] <= n && dis[tmp.first + c[k]][k] > dis[tmp.first][tmp.second] + abs(tmp.second - k) + 2 * abs(c[k])){ // 注意边界特判和转移方程
                dis[tmp.first + c[k]][k] = dis[tmp.first][tmp.second] + abs(tmp.second - k) + 2 * abs(c[k]);
                if (!vis[tmp.first + c[k]][k]){
                    q.push(make_pair(tmp.first + c[k], k));
                    vis[tmp.first + c[k]][k] = 1;
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        cin >> c[i];
        if (c[i] == 0){ // 找到起始的方式
            u = i; 
        }
    }
    spfa();
    for (int i = 1; i <= m; ++i){ // 找最小值
        dis[n][1] = min(dis[n][1], dis[n][i]);
    }
    cout << (dis[n][1] == 0x3f3f3f3f ? -1 : dis[n][1]) << "\n";
}