记录编号	60485	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]海拔	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.468 s
提交时间	2013-05-25 19:29:48	内存使用	5.10 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<queue>
#include<deque>
#include<algorithm>
#include<cmath>
using namespace std;
const int SIZEN=501,SIZEG=501*501,INF=0x7fffffff;
int fp[SIZEN][SIZEN]={0};//人流量
int n;//方块的规模,交点规模是n+1
int N;//图的规模
vector<pair<int,int> > c[SIZEG];//邻接表
//源点是N,汇点是N+1
int f[SIZEG]={0};
int SPFA(int s,int t,int n){//用SPFA会超时一组
	queue<int> Q;
	bool inq[SIZEG]={0};
	int i;
	for(i=0;i<=n;i++) f[i]=0x7fffffff;
	f[s]=0,inq[s]=true,Q.push(s);
	int x,y;
	while(!Q.empty()){
		x=Q.front();Q.pop();
		inq[x]=false;
		for(i=0;i<c[x].size();i++){
			y=c[x][i].first;
			if(f[x]+c[x][i].second<f[y]){
				f[y]=f[x]+c[x][i].second;
				if(!inq[y]){
					Q.push(y);
					inq[y]=true;
				}
			}
		}
	}
	return f[t];
}
int Dijkstra(int s,int t,int n){//堆优化Dijkstra可以AC
	priority_queue<pair<int,int> > Q;
	bool used[SIZEG]={0};
	int i;
	for(i=0;i<=n;i++) f[i]=INF,used[i]=false;
	f[s]=0,Q.push(make_pair(-f[s],s));
	int u,v;
	while(!Q.empty()){
		u=Q.top().second;Q.pop();
		if(!used[u]){
			used[u]=true;
			for(i=0;i<c[u].size();i++){
				v=c[u][i].first;
				if(!used[v]&&f[u]+c[u][i].second<f[v]){
					f[v]=f[u]+c[u][i].second;
					Q.push(make_pair(-f[v],v));
				}
			}
		}
	}
	return f[t];
}
void read(void){
	scanf("%d",&n);
	N=n*n;
	int i,j;
	int fp;
	//方块编号是0~n*n-1
	for(i=0;i<=n;i++){//西东,上到下
		for(j=0;j<n;j++){
			scanf("%d",&fp);
			if(i==0){
				c[N].push_back(make_pair(i*n+j,fp));
			}
			else if(i==n){
				c[(i-1)*n+j].push_back(make_pair(N+1,fp));
			}
			else{
				c[(i-1)*n+j].push_back(make_pair(i*n+j,fp));
			}
		}
	}
	for(i=0;i<n;i++){//北南,右到左
		for(j=0;j<=n;j++){
			scanf("%d",&fp);
			if(j==0){
				c[i*n+j].push_back(make_pair(N+1,fp));
			}
			else if(j==n){
				c[N].push_back(make_pair(i*n+j-1,fp));
			}
			else{
				c[i*n+j].push_back(make_pair(i*n+j-1,fp));
			}
		}
	}
	for(i=0;i<=n;i++){//东西,下到上
		for(j=0;j<n;j++){
			scanf("%d",&fp);
			if(i==0){
				c[i*n+j].push_back(make_pair(N,fp));
			}
			else if(i==n){
				c[N+1].push_back(make_pair((i-1)*n+j,fp));
			}
			else{
				c[i*n+j].push_back(make_pair((i-1)*n+j,fp));
			}
		}
	}
	for(i=0;i<n;i++){//南北,左到右
		for(j=0;j<=n;j++){
			scanf("%d",&fp);
			if(j==0){
				c[N+1].push_back(make_pair(i*n+j,fp));
			}
			else if(j==n){
				c[i*n+j-1].push_back(make_pair(N,fp));
			}
			else{
				c[i*n+j-1].push_back(make_pair(i*n+j,fp));
			}
		}
	}
}
int main(){
	freopen("altitude.in","r",stdin);
	freopen("altitude.out","w",stdout);
	read();
	cout<<Dijkstra(N,N+1,N+1)<<endl;
	return 0;
}