记录编号	140642	评测结果	AAAAAA
题目名称	[BJOI2006] 狼抓兔子	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.609 s
提交时间	2014-11-22 21:38:30	内存使用	32.73 MiB

#include <iostream>
#include <cctype>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
inline void getd(int &x){
	char c = getchar();
	bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*======================================================*/
const int maxn = 2000003, INF = 0x3f3f3f3f;
#define pb push_back
struct edge{
	int to, w;
	edge(int t, int W):to(t), w(W){}
};
vector<edge> adj[maxn];
int N, M, To, dis[maxn] = {0};

inline void init(){
	int i, j, k, t, d;
	getd(N), getd(M);
	To = ((N-1) * (M-1) * 2) + 1;
	//横向道路
	d = 2 * M - 3;
	for(i = k = 1;i < M;++i, k+=2){
		getd(t);
		adj[0].pb(edge(k, t));
	}
	for(i = 2;i < N;++i){
		for(j = 1;j < M;++j, k+=2){
			getd(t);
			adj[k].pb(edge(k-d, t));
			adj[k-d].pb(edge(k, t));
		}
	}
	for(j = 1, k = To-2*(M-2)-1;j < M;++j, k+=2){
		getd(t);
		adj[k].pb(edge(To, t));
	}
	//纵向道路
	for(i = 1,k = 2;i < N;++i){
		getd(t);
		adj[k].pb(edge(To, t));
		for(j = 2,k+=2;j < M;++j,k+=2){
			getd(t);
			adj[k].pb(edge(k-3, t));
			adj[k-3].pb(edge(k, t));
		}
		getd(t);
		adj[0].pb(edge(k-3, t));
	}
	//斜向道路
	for(i = 1, k = 1;i < N;++i){
		for(j = 1;j < M;++j, k += 2){
			getd(t);
			adj[k].pb(edge(k+1, t));
			adj[k+1].pb(edge(k, t));
		}
	}
	for(i = 1;i <= To;++i)
		dis[i] = INF;
}
queue<int> Q;
bool inQ[maxn] = {1};
inline void work(){
	Q.push(0);
	int t;
	vector<edge>::iterator it;
	while(!Q.empty()){
		t = Q.front();Q.pop();inQ[t] = 0;
		for(it = adj[t].begin();it != adj[t].end();++it)
			if(dis[t] + it->w < dis[it->to]){
				dis[it->to] = dis[t] + it->w;
				if(!inQ[it->to])
					Q.push(it->to), inQ[it->to] = 1;
			}
	}
	printf("%d\n", dis[To]);
}

int main(){
	//#if defined DEBUG
	//freopen("test", "r", stdin);
	//#endif
	freopen("bjrabbit.in", "r", stdin);
	freopen("bjrabbit.out", "w", stdout);
	
	init();
	
	work();
	
	#if defined DEBUG
	cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}