算法

(Dijkstra) $O(hw\log(hw))$

直接用 Dijkstra 跑一遍 $(1, 1)$ 到 $(h, w)$ 的最短路即可。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using std::greater;
using std::priority_queue;
using P = std::pair<int, int>;

int main() {
    int h, w;
    cin >> h >> w;

    vector<vector<int>> a(h, vector<int>(w - 1));
    vector<vector<int>> b(h - 1, vector<int>(w));
    rep(i, h)rep(j, w - 1) cin >> a[i][j];
    rep(i, h - 1)rep(j, w) cin >> b[i][j];

    const int INF = 1001001001;
    priority_queue<P, vector<P>, greater<P>> q;
    vector<int> dist(h * w * 2, INF);
    auto push = [&](int i, int j, int k, int x) {
        int v = i * w * 2 + j * 2 + k;
        if (dist[v] <= x) return;
        dist[v] = x;
        q.emplace(x, v);
    };
    push(0, 0, 0, 0);
    while (!q.empty()) {
        auto [x, v] = q.top(); q.pop();
        if (dist[v] != x) continue;
        int i = v / (w * 2);
        int j = v / 2 % w;
        int k = v % 2;
        if (k == 0) {
            if (j + 1 < w) push(i, j + 1, k, x + a[i][j]);
            if (j - 1 >= 0) push(i, j - 1, k, x + a[i][j - 1]);
            if (i + 1 < h) push(i + 1, j, k, x + b[i][j]);
            push(i, j, 1, x + 1);
        }
        else {
            if (i - 1 >= 0) push(i - 1, j, k, x + 1);
            push(i, j, 0, x);
        }
    }

    int ans = dist[(h * w - 1) * 2];
    cout << ans << '\n';

    return 0;
}