P11952 行走题解

sunqihuan · 2025-10-23 22:28:18 · 题解

一道非常经典和锻炼人的 dp 题，建议一定好好做。

先理清题目：有一个网格，每条边都有一个边权，存储方式如下：

然后每次删去一条边，求最短路。

先放代码，思路最好结合来理解：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
// 全局变量 seed 和 B
unsigned long long seed;
int B;

const long long N = 5005, inf = 1e16;

long long f[N][N], f2[N][N], ea[N][N], eb[N][N];

// xorshift64 算法，不能修改
unsigned long long xorshift64(){
    seed ^= seed << 13;
    seed ^= seed >> 7;
    seed ^= seed << 17;
    return seed;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    cin >> seed >> B;

    // 生成横向边权：遍历 i=1..n, j=1..n-1
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n-1; j++){
            xorshift64();
            ea[i][j] = seed & ((1ULL << B) - 1);
        }
    }

    // 生成纵向边权：遍历 i=1..n-1, j=1..n
    for (int i = 1; i <= n-1; i++){
        for (int j = 1; j <= n; j++){
            xorshift64();
            eb[i][j] = seed & ((1ULL << B) - 1);
        }
    }
    // 你可以从这里开始编写你的代码

    for (int i = 2; i <= n; i ++ ) f[1][i] = f[1][i - 1] + ea[1][i - 1];
    for (int i = 2; i <= n; i ++ ) f[i][1] = f[i - 1][1] + eb[i - 1][1];
    for (int i = n - 1; i >= 1; i -- ) f2[n][i] = f2[n][i + 1] + ea[n][i];
    for (int i = n - 1; i >= 1; i -- ) f2[i][n] = f2[i + 1][n] + eb[i][n];
    for (int i = 2; i <= n; i ++ )
        for (int j = 2; j <= n; j ++ )
            f[i][j] = min(f[i - 1][j] + eb[i - 1][j], f[i][j - 1] + ea[i][j - 1]);
    for (int i = n - 1; i >= 1; i -- )
        for (int j = n - 1; j >= 1; j -- )
            f2[i][j] = min(f2[i][j + 1] + ea[i][j], f2[i + 1][j] + eb[i][j]);
    for (int i = 0; i <= n + 1; i ++ )
        for (int j = 0; j <= n + 1; j ++ )
        {
            if (i < 1 || j < 1 || i > n || j >= n) ea[i][j] = inf;
            if (i < 1 || j < 1 || i >= n || j > n) eb[i][j] = inf;
        }    
    for (int j = 1; j <= n; j ++ )
        for (int i = n; i >= 1; i -- )
            ea[i][j] = min(ea[i + 1][j], f[i][j] + ea[i][j] + f2[i][j + 1]);
    for (int i = 1; i <= n; i ++ )
        for (int j = n; j >= 1; j -- )
            eb[i][j] = min(eb[i][j + 1], f[i][j] + eb[i][j] + f2[i + 1][j]);
    while (q -- )
    {
        int x, y, xx, yy;
        cin >> x >> y >> xx >> yy;
        if (x == xx) cout << min(ea[x + 1][y], eb[x - 1][y + 1]) << "\n";
        else cout << min(eb[x][y + 1], ea[x + 1][y - 1]) << "\n";
    }
    return 0;
}

如果没有删边的话，那这道题就是一道简单的动规题目，转移方程就是 f_{i,j}=\min(f_{i-1,j}+eb_{i-1,j},f_{i,j-1}+ea_{i,j-1})

但是有删边。考虑到一定经过一条边 (x,y)(x_2,y_2) 的最小权值就是从起点到 (x,y) 的最小权值加上边权加上从 (x_2,y_2) 到终点的最小权值。所以想到要处理后缀，转移方程很相似。这样我们就写出了 f 和 f_2 数组。

下一步就是在 ea 和 eb 上做 dp，所以先把周围都清除成无穷大。（这里有一个坑点就是一开始 ea,eb 的大小只到 n，如果再加一就会 RE，所以前面的定义要改）

这里的含义变了（重中之重！），设 ea/eb_{x,y} 表示的意义为“跨越某条切口（横/纵）的最短绕行代价”，从直接穿过和向右/下绕行取最小值，所以转移方程显而易见。

接下来的难点是如何求答案。先看去掉 (x,y)(x,y+1) 的情况。

可以发现，想要绕过断掉的边，就只能在这两条边上不断向下/右绕，取最小值即可。

如果是断掉竖着的边那就整个反过来就行了，主要看代码。

感觉好像表达的并不是很通畅（？）如果有更多的意见和方法希望能在评论区留言，我也很希望能更深入理解这道题目。

P11952 行走 题解

P11952 行走题解