这题 acwing 怎么还没有题解？

容易发现海拔一定是 $0$ 或 $1$。
于是容易想到最小割。
于是转最大流，做完了。

然后你会惊喜地发现数据范围貌似并不能 dinic 干过去（没实测过），于是我去学了一下平面图转对偶图。
然后跑 dijkstra 就做完了。

#include <bits/stdc++.h>
using namespace std;
const int N = 255015, M = N << 3;
int h[N], e[M], w[M], ne[M], idx = 0;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int S = 0, T = 0;
int n, d[N];
bool st[N];
priority_queue< pair<int, int> > q;

void dijkstra() {
    for (int i = S; i <= T; i++) st[i] = 0, d[i] = 0x3f3f3f3f;
    d[S] = 0;
    q.push(make_pair(0, S));
    while (q.size()) {
        int u = q.top().second; q.pop();
        if (st[u]) continue;
        st[u] = 1;

        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (d[v] > d[u] + w[i]) {
                d[v] = d[u] + w[i];
                q.push(make_pair(-d[v], v));
            }
        }
    }
}

int id(int x, int y) {
    if (x == 0 || y == n) return S;
    if (x == n || y == 0) return T;
    return (x - 1) * n + y;
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d", &n), n++;
    S = 0, T = N - 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1, c; j < n; j++) {
            scanf("%d", &c);
            int a = id(i - 1, j), b = id(i, j);
            add(a, b, c);
        }
    for (int i = 1, c; i < n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &c);
            int a = id(i, j), b = id(i, j - 1);
            add(a, b, c);
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1, c; j < n; j++) {
            scanf("%d", &c);
            int a = id(i, j), b = id(i - 1, j);
            add(a, b, c);
        }
    for (int i = 1, c; i < n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &c);
            int a = id(i, j - 1), b = id(i, j);
            add(a, b, c);
        }
    dijkstra();
    printf("%d\n", d[T]);
    return 0;
}