• 平面图最短路（对偶图） 对于矩阵图，建立对偶图的过程如下（注释部分为建立原图），其中数据的给出顺序依次为：各$n(n+1)$个数字分别代表从左向右、从上向下、从右向左、从下向上的边。

时间复杂度： $O(n^{2}logn)$空间复杂度： $O(n^2)$

using ll = long long;

struct Edge {
    int to;
    ll w;
};

int n, s, t;
vector<vector<Edge>> adj;

inline int Hash(int i, int j) {
    return (i - 1) * n + j;
}

inline void add(int u, int v, ll w) {
    adj[u].push_back({v, w});
}

// 平面图转对偶图建图模板
void build_dual_graph() {
    s = 0, t = n * n + 1;
    adj.assign(t + 1, {});

    // 1. 左 -> 右 的边：连接 上面 -> 下面
    for (int i = 1; i <= n + 1; ++i) {
        for (int j = 1; j <= n; ++j) {
            ll w; cin >> w;
            int u = (i == 1) ? s : Hash(i - 1, j);
            int v = (i == n + 1) ? t : Hash(i, j);
            add(u, v, w);
        }
    }

    // 2. 上 -> 下 的边：连接 右面 -> 左面
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n + 1; ++j) {
            ll w; cin >> w;
            int u = (j == n + 1) ? s : Hash(i, j);
            int v = (j == 1) ? t : Hash(i, j - 1);
            add(u, v, w);
        }
    }

    // 3. 右 -> 左 的边：连接 下面 -> 上面
    for (int i = 1; i <= n + 1; ++i) {
        for (int j = 1; j <= n; ++j) {
            ll w; cin >> w;
            int u = (i == n + 1) ? t : Hash(i, j);
            int v = (i == 1) ? s : Hash(i - 1, j);
            add(u, v, w);
        }
    }

    // 4. 下 -> 上 的边：连接 左面 -> 右面
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n + 1; ++j) {
            ll w; cin >> w;
            int u = (j == 1) ? t : Hash(i, j - 1);
            int v = (j == n + 1) ? s : Hash(i, j);
            add(u, v, w);
        }
    }
}