记录编号	239745	评测结果	AAAAAA
题目名称	[BJOI2006] 狼抓兔子	最终得分	100
用户昵称	asddddd	是否通过	通过
代码语言	C++	运行时间	1.072 s
提交时间	2016-03-20 15:37:23	内存使用	59.44 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#define maxn 3100000
using namespace std;
vector<int>G[maxn];
void addedge(int from,int to){
	G[from].push_back(to);
	G[to].push_back(from);
}
int n,m,t;
int cost[maxn],dist[maxn];
void spfa(int s){
	bool inq[maxn];
	queue<int>que;
	memset(inq,0,sizeof(inq));
	memset(dist,-1,sizeof(dist));
	dist[s]=0;
	que.push(s);
	while(!que.empty()){
		int k=que.front();
		que.pop();
		inq[k]=0;
		for(int i=0;i<G[k].size();i++){
			int u=G[k][i];
			if(dist[u]>dist[k]+cost[u]||dist[u]==-1){
				dist[u]=dist[k]+cost[u];
				if(!inq[u]){
					que.push(u);
					inq[u]=1;
				}
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	freopen("bjrabbit.in","r",stdin);
	freopen("bjrabbit.out","w",stdout);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=1;j<=m-1;j++){
			cin>>cost[i*(2*m-1)+j];
		}
	}
	
	for(int i=0;i<n-1;i++){
		for(int j=1;j<=m;j++){
			cin>>cost[m-1+i*(2*m-1)+j];
		}
	}
	t=n*(m-1)+(n-1)*m+1;
	
	for(int i=0;i<n-1;i++){
		for(int j=1;j<=m-1;j++){
			cin>>cost[t];
			addedge(t,i*(2*m-1)+j);
			addedge(t,m-1+i*(2*m-1)+j+1);
			addedge(i*(2*m-1)+j,m-1+i*(2*m-1)+j+1);
			addedge(t,(i+1)*(2*m-1)+j);
			addedge(t,m-1+i*(2*m-1)+j);
			addedge((i+1)*(2*m-1)+j,m-1+i*(2*m-1)+j);
			t++;
		}
	}
	for(int i=0;i<n-1;i++){
		addedge(0,m+i*(2*m-1));
		addedge(t,(i+1)*(2*m-1));
	}
	for(int i=1;i<=m-1;i++){
		addedge(0,(n-1)*(2*m-1)+i);
		addedge(i,t);
	}
	spfa(0);
	cout<<dist[t];
}