RT,Dij+拆点。

WA#1#3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N=157;
const int M=301;
const int inf=1e18;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
bool vis[N][N][M];
int n,m,a[N][N],b[N][N],xg[4],yg[4];
struct node{
    int x,y,k,val;
    inline bool operator < (const node &X)const{return val>X.val;}
};
priority_queue<node>q;
int f[N][N][M];
inline void Dij(int s){
	for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k <= n + m; k++)
                vis[i][j][k] = 0,f[i][j][k]=inf;
    while(!q.empty())q.pop();
    
    f[xg[s]][yg[s]][0]=0;
    q.push({xg[s],yg[s],0,0});
    while(!q.empty()){
    	node X=q.top();
    	q.pop();
    	int x=X.x,y=X.y,k=X.k;
    	if(vis[x][y][k])continue;
    	vis[x][y][k]=1;
    	if(f[x][y][b[x][y]]>f[x][y][k]+a[x][y]){
    		f[x][y][b[x][y]]=f[x][y][k]+a[x][y];
    		q.push({x,y,b[x][y],f[x][y][b[x][y]]});
		}
		for(int i=0;i<4;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx<1||ny<1||nx>n||ny>n)continue;
			if(k>0&&f[nx][ny][k-1]>f[x][y][k]){
				f[nx][ny][k-1]=f[x][y][k];
				q.push({nx,ny,k-1,f[nx][ny][k-1]});
			}
		}
	}
    return;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)cin>>b[i][j],b[i][j]=min(b[i][j],max(i-1ll,n-i)+max(j-1ll,m-j));
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)cin>>a[i][j];
	for(int i=1;i<=3;i++)cin>>xg[i]>>yg[i];
	Dij(1);
	int a1 = f[xg[2]][yg[2]][0],a2 = f[xg[3]][yg[3]][0];
	for(int i=1;i<=n+m;i++)a1=min(a1,f[xg[2]][yg[2]][i]),a2=min(a2,f[xg[3]][yg[3]][i]);
	Dij(2);
	int b1 = f[xg[1]][yg[1]][0],b2 = f[xg[3]][yg[3]][0];
	for(int i=1;i<=n+m;i++)b1=min(b1,f[xg[1]][yg[1]][i]),b2=min(b2,f[xg[3]][yg[3]][i]);
	Dij(3);
	int c1 = f[xg[2]][yg[2]][0],c2 = f[xg[1]][yg[1]][0];
	for(int i=1;i<=n+m;i++)c1=min(c1,f[xg[2]][yg[2]][i]),c2=min(c2,f[xg[1]][yg[1]][i]);
	char ch;
	int res=inf;
	if(res>b1+c2){
		res=b1+c2;
		ch='X'; 
	}
	if(res>a1+c1){
		res=a1+c1;
		ch='Y';
	}
	if(res>b2+a2){
		res=b2+a2;
		ch='Z';
	}
	if(res==inf){
		puts("NO");
		return 0;
	}
	cout<<ch<<"\n"<<res;
}