平面图最短路（对偶图）
对于矩阵图，建立对偶图的过程如下（注释部分为建立原图），其中数据的给出顺序依次为：各 \(n(n+1)\) 个数字分别代表从左向右、从上向下、从右向左、从下向上的边。
for (int i = 1; i <= n + 1; i++) {for (int j = 1, w; j <= n; j++) {cin >> w;int pre = Hash(i - 1, j), now = Hash(i, j);if (i == 1) {add(s, now, w);} else if (i == n + 1) {add(pre, t, w);} else {add(pre, now, w);}// flow.add(Hash(i, j), Hash(i, j + 1), w);}
}
for (int i = 1; i <= n; i++) {for (int j = 1, w; j <= n + 1; j++) {cin >> w;int now = Hash(i, j), net = Hash(i, j - 1);if (j == 1) {add(now, t, w);} else if (j == n + 1) {add(s, net, w);} else {add(now, net, w);}// flow.add(Hash(i, j), Hash(i + 1, j), w);}
}
for (int i = 1; i <= n + 1; i++) {for (int j = 1, w; j <= n; j++) {cin >> w;int now = Hash(i, j), net = Hash(i - 1, j);if (i == 1) {add(now, s, w);} else if (i == n + 1) {add(t, net, w);} else {add(now, net, w);}// flow.add(Hash(i, j), Hash(i, j - 1), w);}
}
for (int i = 1; i <= n; i++) {for (int j = 1, w; j <= n + 1; j++) {cin >> w;int pre = Hash(i, j - 1), now = Hash(i, j);if (j == 1) {add(t, now, w);} else if (j == n + 1) {add(pre, s, w);} else {add(pre, now, w);}// flow.add(Hash(i, j), Hash(i - 1, j), w);}
}