记录编号	373406	评测结果	AAAAAA
题目名称	[BJOI2006] 狼抓兔子	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.093 s
提交时间	2017-02-21 06:10:01	内存使用	94.75 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
const int maxn=1005*1005*2,INF=0x3f3f3f3f;
char cc;inline void R_int(int &x){
	while(cc=getchar(),cc<'!');x=cc-48;
	while(cc=getchar(),cc>'!')x=x*10+cc-48;
}
struct Rabit_tree{int to,next,dis;}e[maxn*3+4005];
int n,m,N=0,S=0,T,head[maxn],len=1,pos[1005][1005][2],sb=INF;
inline void Rabit_set(int prt,int son,int dis){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len,e[len].dis=dis,sb=min(sb,dis);
}
#define to e[i].to
int dis[maxn];bool bein[maxn];deque<int>q;
int Rabit_run(){
	int rt,i;bein[S]=true;q.push_back(S);
	for(i=1;i<=T;i++)dis[i]=INF;dis[S]=0;
	while(!q.empty()){
		rt=q.front(),q.pop_front();bein[rt]=false;
		for(i=head[rt];i;i=e[i].next)
			if(dis[to]>dis[rt]+e[i].dis){
				dis[to]=dis[rt]+e[i].dis;
				if(!bein[to]){
					bein[to]=true;
					if(q.empty()||dis[q.front()]<dis[to])q.push_back(to);
					else q.push_front(to);
				}
			}
	}
	return dis[T];
}
int main(){
	freopen("bjrabbit.in","r",stdin);freopen("bjrabbit.out","w",stdout);
	R_int(n),R_int(m);int i,j,x;
	
	for(i=1;i<n;i++)
	for(j=1;j<m;j++)
		pos[i][j][0]=++N,pos[i][j][1]=++N;
	T=N+1;
	
	for(i=1;i<n;i++)
	for(j=1;j<m;j++)
		R_int(x),Rabit_set(pos[i-1][j][1],pos[i][j][0],x);
	for(i=1;i<m;i++)
		R_int(x),Rabit_set(pos[n-1][i][1],T,x);
	
	for(i=1;i<n;i++){
		R_int(x),Rabit_set(pos[i][1][1],T,x);
		for(j=2;j<=m;j++)
			R_int(x),Rabit_set(pos[i][j][1],pos[i][j-1][0],x);
	}
	
	for(i=1;i<n;i++)
	for(j=1;j<m;j++)
		R_int(x),Rabit_set(pos[i][j][0],pos[i][j][1],x);
	
	if(n==1&&m==1)sb=0;
	if(n==1||m==1)printf("%d\n",sb);
	else printf("%d\n",Rabit_run());
}