记录编号	254762	评测结果	AAAAAA
题目名称	[BJOI2006] 狼抓兔子	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.315 s
提交时间	2016-04-25 19:05:49	内存使用	158.68 MiB

/*****************************************************
平面图最小割转化为对偶图最短路，spfa裸上
注意内存！
*****************************************************/
#include<stdio.h>
#include<string.h>
inline void in(int &x){for(x=getchar();x<48||x>57;x=getchar());x^=48;for(int tmp=getchar();47<tmp&&tmp<58;tmp=getchar())x=(x<<1)+(x<<3)+(tmp^48);}
int n,m,w,shu,cnt,id[1010][1010],first[2000010];
struct edge{int v,w,nx;}o[6000010];
inline void add(int u,int v,int w){
	o[++shu].v=v,o[shu].w=w,o[shu].nx=first[u],first[u]=shu;
	o[++shu].v=u,o[shu].w=w,o[shu].nx=first[v],first[v]=shu;
}
bool flag[2000010];
int l,r,x,q[18000010],d[2000010];
void spfa(){
	memset(d,0x3f,sizeof(d)),d[0]=0;
	while(l<=r){
		x=q[l++],flag[x]=0;
		for(int i=first[x];i;i=o[i].nx)
			if(d[o[i].v]>d[x]+o[i].w){
				d[o[i].v]=d[x]+o[i].w;
				if(!flag[o[i].v])flag[o[i].v]=1,q[++r]=o[i].v;
			}
	}
}
int main(){
	freopen("bjrabbit.in","r",stdin);
	freopen("bjrabbit.out","w",stdout);
	in(n),in(m);
	if(n==1||m==1){
		if(n>m)n^=m,m^=n,n^=m;
		int ans=0x3fffffff;
		for(int i=1,w;i<m;++i)
		    in(w),ans=ans>w?w:ans;
		return printf("%d\n",ans==0x3fffffff?0:ans),0;
	}
	for(int i=1;i<n;++i)
	    for(int j=1;j<m;++j)
	        cnt+=2,id[i][j]=cnt;
	for(int i=1,w;i<=n;++i)
	    for(int j=1;j<m;++j){
			in(w);
			if(i==1)add(id[i][j]|1,1,w);
			else if(i==n)add(0,id[i-1][j],w);
			else add(id[i][j]|1,id[i-1][j],w);
	    }
	for(int i=1,w;i<n;++i)
	    for(int j=1;j<=m;++j){
			in(w);
			if(j==1)add(0,id[i][j],w);
			else if(j==m)add(id[i][j-1]|1,1,w);
			else add(id[i][j-1]|1,id[i][j],w);
	    }
	for(int i=1,w;i<n;++i)
	    for(int j=1;j<m;++j)
			in(w),add(id[i][j],id[i][j]|1,w);
	spfa();
	printf("%d",d[1]);
	//while(1);
}