记录编号	427410	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]飞飞侠	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	11.210 s
提交时间	2017-07-21 19:47:24	内存使用	2.79 MiB

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>

using namespace std;

typedef long long LL;

void read(int &x) {
    char c;bool flag = 0;
    while((c=getchar())<'0'||c>'9') flag |= (c=='-');
    x=c-'0';while((c=getchar())>='0'&&c<='9') x = (x<<3)+(x<<1)+c-'0';
    flag?x=-x:x;
}

#define N 403

int d[N][N],inq[N][N],a[N][N],b[N][N];
int n,m,s,cas,cost;

struct pii{int x,y;};
queue<pii> q;

int x[11],y[11];

int dis[5][5];

void spfa(int s) {
    memset(d,127/3,sizeof(d));
    q.push((pii){x[s],y[s]}); d[x[s]][y[s]] = 0;
    while (q.size()) {
        pii t = q.front(); q.pop(); inq[t.x][t.y] = 0;
        int val = d[t.x][t.y]+a[t.x][t.y],le = b[t.x][t.y];
        for (int i = max(1,t.x-le); i <= min(n,t.x+le); i++) { 
         int det = le-abs(i-t.x);
         for (int j = max(1,t.y-det); j <= min(m,t.y+det); j++)
          if(d[i][j] > val) {
          	  d[i][j] = val;
          	  if(!inq[i][j]) {
          	     inq[i][j] = 1;
				 q.push((pii){i,j});  	
			  } 
		  } 
		} 
    }
	for (int i = 1; i <= 3; i++) dis[s][i] = d[x[i]][y[i]];
}

int main() {
    freopen("nt2011_fly.in","r",stdin);freopen("nt2011_fly.out","w",stdout);
    read(n); read(m);
	for (int i = 1; i <= n; i++)
	 for (int j = 1; j <= m; j++)
	   read(b[i][j]);
	for (int i = 1; i <= n; i++)
   	 for (int j = 1; j <= m; j++)
   	   read(a[i][j]);
	for (int i = 1; i <= 3; i++) read(x[i]),read(y[i]);
	spfa(1); spfa(2); spfa(3); cost = d[0][0];
	
	for (int i = 1; i <= 3; i++) {
		int tp = dis[1][i]+dis[2][i]+dis[3][i];
//cout <<dis[1][i] <<" "<<dis[2][i] <<" "<<dis[3][i] <<"\n";
		if(tp < cost) {
			cost = tp;
			cas = i;
		}
	}
	
	if(cost == d[0][0]) {
		puts("NO");
		return 0;
	}
	printf("%c\n%d",'X'+char(cas-1),cost);
    return 0;
}