同1001一样，对偶图最小割转最短路
又被卡spfa= =
话说为什么总是有些人总喜欢卡spfa，又好写一般情况又快，为何老是要逼人写迪杰斯特拉= =
要就题目直接说会卡spfa嘛
好吧其实是前几天考试被spfa卡掉一半点发牢骚的= =不要介意= =
话说最近真的有些背，各种卡时卡空间（差2MB就过了的惨痛经历啊QAQ）
好吧不说那么多了= =
CODE：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define maxk 510
#define maxn maxk*maxk
#define maxm maxn*4
#define inf 0x7fffffff
struct edges{
int to,next,dist;
}edge[maxm];
struct node{
int u,v;
};
bool operator < (node x,node y) {
return x.v>y.v;
}
int l,next[maxn];
void addedge(int x,int y,int z){
edge[++l]=(edges){y,next[x],z};next[x]=l;
}
int dist[maxn],s,t;
bool b[maxn];
priority_queue<node > q;
int spfa(){
for (int i=1;i<=t;i++) dist[i]=inf;
dist[s]=0;
q.push((node){s,0});
while (!q.empty()) {
node x=q.top();q.pop();
int u=x.u;
if (b[u]) continue;
b[u]=1;
for (int i=next[u];i;i=edge[i].next)
if (dist[edge[i].to]>dist[u]+edge[i].dist) {
dist[edge[i].to]=dist[u]+edge[i].dist;
q.push((node){edge[i].to,dist[edge[i].to]});
}
}
return dist[t];
}
int n,x,id[maxk][maxk],cnt;
int main(){
scanf("%d",&n);
n++;
for (int i=1;i<n;i++)
for (int j=1;j<n;j++) id[i][j]=++cnt;
s=++cnt,t=++cnt;
for (int i=1;i<=n;i++)
for (int j=1;j<n;j++) {
scanf("%d",&x);
addedge(i==1?s:id[i-1][j],i==n?t:id[i][j],x);
}
for (int i=1;i<n;i++)
for (int j=1;j<=n;j++) {
scanf("%d", &x);
addedge(j==n?s:id[i][j],j==1?t:id[i][j-1],x);
}
for (int i=1;i<=n;i++)
for (int j=1;j<n;j++) {
scanf("%d",&x);
addedge(i==n?t:id[i][j],i==1?s:id[i-1][j],x);
}
for (int i=1;i<n;i++)
for (int j=1;j<=n;j++) {
scanf("%d",&x);
addedge(j==1?t:id[i][j-1],j==n?s:id[i][j],x);
}
printf("%d ",spfa());
return 0;
}