记录编号	141726	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]飞飞侠	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	18.836 s
提交时间	2014-12-03 20:18:52	内存使用	315.94 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<deque>
using namespace std;
const int SIZEn=160,SIZEN=6750010,INF=0x7fffffff/2;
int N;//0~N
int n,m;
int x[3],y[3];
int hash(int x,int y,int h){
	return h*(m*n)+(x*m+y);
}
int dx[10]={0,0,0,1,-1},dy[10]={0,1,-1,0,0};
int A[SIZEn][SIZEn]={0},B[SIZEn][SIZEn]={0};
pair<int,int> c[SIZEN][5];
int len[SIZEN]={0};
int f[SIZEN]={0};
bool used[SIZEN]={0};
priority_queue<pair<int,int> > Q;
void Dijkstra(int S,int t1,int t2){
	for(int i=0;i<N;i++) f[i]=INF;
	memset(used,0,sizeof(used));
	while(!Q.empty()) Q.pop();
	f[S]=0,Q.push(make_pair(-f[S],S));
	while(!Q.empty()){
		int x=Q.top().second;Q.pop();
		if(!used[x]){
			used[x]=true;
			for(int i=0;i<len[x];i++){
				int v=c[x][i].first;
				if(!used[v]&&f[x]+c[x][i].second<f[v]){
					f[v]=f[x]+c[x][i].second;
					Q.push(make_pair(-f[v],v));
				}
			}
		}
		if(used[t1]&&used[t2]) return;
	}
}
void addedge(int a,int b,int w){
	c[a][len[a]++]=make_pair(b,w);
}
void makegraph(void){
	N=n*m*(n+m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			addedge(hash(i,j,0),hash(i,j,min(B[i][j],n+m-1)),A[i][j]);
			for(int h=1;h<n+m;h++){
				for(int d=0;d<5;d++){
					int i1=i+dx[d],j1=j+dy[d];
					if(0<=i1&&i1<n&&0<=j1&&j1<m){
						addedge(hash(i,j,h),hash(i1,j1,h-1),0);
					}
				}
			}
		}
	}
}
void work(void){
	int mp[3]={0};
	int dis[3][3]={0};
	for(int i=0;i<3;i++) mp[i]=hash(x[i],y[i],0);
	Dijkstra(mp[0],mp[1],mp[2]);
	dis[0][1]=f[mp[1]],dis[0][2]=f[mp[2]];
	Dijkstra(mp[1],mp[0],mp[2]);
	dis[1][0]=f[mp[0]],dis[1][2]=f[mp[2]];
	Dijkstra(mp[2],mp[0],mp[1]);
	dis[2][0]=f[mp[0]],dis[2][1]=f[mp[1]];
	int id=-1,ans=INF;
	for(int i=0;i<3;i++){
		int now=0;
		for(int j=0;j<3;j++) now+=dis[j][i];
		if(now<ans) id=i,ans=now;
	}
	if(id==-1) cout<<"NO"<<endl;
	else{
		char pos='X'+id;
		cout<<pos<<endl<<ans<<endl;
	}
}
void read(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&B[i][j]);
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&A[i][j]);
	for(int i=0;i<3;i++) scanf("%d%d",&x[i],&y[i]),x[i]--,y[i]--;
}
int main(){
	freopen("nt2011_fly.in","r",stdin);
	freopen("nt2011_fly.out","w",stdout);
	read();
	makegraph();
	work();
	return 0;
}