分析
就是飞飞侠这道题......
我们可以将这张图建成好几层，每一层可以向下一层的上下左右无代价移动，而对于每个点如果付b[i][j]的代价就可以走到比它高a[i][j]的层上。我们用这种方式优化了建边，然后跑个最短路就行了。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define ri register int
const long long inf = 1e12+7;
const int dx[5] = {1,-1,0,0,0};
const int dy[5] = {0,0,1,-1,0};
inline int ra(){
int x=0;char s=getchar();while(!isdigit(s))s=getchar();
while(isdigit(s)){x=(x<<3)+(x<<1)+(s-'0');s=getchar();}return x;
}
inline long long ra2(){
long long x=0;char s=getchar();while(!isdigit(s))s=getchar();
while(isdigit(s)){x=(x<<3)+(x<<1)+(s-'0');s=getchar();}return x;
}
struct node {long long wh;int x,y,z;};
bool operator < (node p,node q){return p.wh>q.wh;}
int n,m,a[210][210],vis[210][210][420],x[4],y[4];
priority_queue<node>q;
long long b[210][210],d[210][210][420],w[4];
inline void dij(int s,int t1,int t2){
node A,B;
for(ri i=1;i<=n;++i)
for(ri j=1;j<=m;++j)
for(ri k=0;k<=n+m;++k)d[i][j][k]=inf,vis[i][j][k]=0;
while(!q.empty())q.pop();
d[x[s]][y[s]][0]=0;
A.wh=0,A.x=x[s],A.y=y[s],A.z=0;
q.push(A);
while(!q.empty()){
if(vis[x[0]][y[0]][0]&&vis[x[1]][y[1]][0]&&vis[x[2]][y[2]][0])
break;
A=q.top();q.pop();
if(vis[A.x][A.y][A.z])continue;
vis[A.x][A.y][A.z]=1;
if(A.z>0){
for(ri i=0;i<5;++i){
if(dx[i]+A.x<1||dx[i]+A.x>n)continue;
if(dy[i]+A.y<1||dy[i]+A.y>m)continue;
if(d[A.x+dx[i]][A.y+dy[i]][A.z-1]>A.wh){
d[A.x+dx[i]][A.y+dy[i]][A.z-1]=A.wh;
B.x=A.x+dx[i],B.y=A.y+dy[i],B.z=A.z-1,B.wh=A.wh;
q.push(B);
}
}
}else {
if(d[A.x][A.y][a[A.x][A.y]]>A.wh+b[A.x][A.y]){
d[A.x][A.y][a[A.x][A.y]]=A.wh+b[A.x][A.y];
B.x=A.x,B.y=A.y,B.z=a[A.x][A.y],B.wh=A.wh+b[A.x][A.y];
q.push(B);
}
}
}
w[t1]+=d[x[t1]][y[t1]][0],w[t2]+=d[x[t2]][y[t2]][0];
return;
}
int main(){
int out;
n=ra(),m=ra();
for(ri i=1;i<=n;++i)
for(ri j=1;j<=m;++j)
a[i][j]=ra(),a[i][j]=min(a[i][j],n+m);
for(ri i=1;i<=n;++i)
for(ri j=1;j<=m;++j)
b[i][j]=ra2();
for(ri i=0;i<3;++i)x[i]=ra(),y[i]=ra();
long long minn=inf;
dij(0,1,2),dij(1,0,2),dij(2,0,1);
if(w[0]<minn)minn=w[0],out=0;
if(w[1]<minn)minn=w[1],out=1;
if(w[2]<minn)minn=w[2],out=2;
if(minn>=inf)puts("NO");
else cout<<char(out+'X')<<endl<<minn<<endl;
return 0;
}