同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\n",spfa());

    return 0;

}