Lvat_s Blog

首先你会发现这是一个最短路

然后你会发现边数太多了

然后就不会了

hzwer教导我们：不连边也能跑最短路

具体就是设定一个高度不断下降，像分层图那么搞就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
const int N=155,INF=1000000000,dx[]={1,-1,0,0,0},dy[]={0,0,-1,1,0};
 
int n,m,A[N][N],B[N][N],X[5],Y[5],D[N][N][N<<1],ans=INF,flag,num,a1,a2,b1,b2,c1,c2;
bool vis[N][N][N<<1];
 
struct Data{
int v,x,y,s;
Data(int vs,int xs,int ys,int ss){v=vs;x=xs;y=ys;s=ss;}
friend bool operator<(Data A,Data B){return A.v>B.v;}
};
 
priority_queue<Data> PQ;
 
void Dijkstra(int Xs,int Ys){
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        for(int k=0;k<=num;k++){
            D[i][j][k]=INF;
            vis[i][j][k]=0;
        }
    }
}
D[Xs][Ys][B[Xs][Ys]]=A[Xs][Ys];
while(!PQ.empty())PQ.pop();
vis[Xs][Ys][0]=1;
PQ.push(Data(A[Xs][Ys],Xs,Ys,B[Xs][Ys]));
while(!PQ.empty() && !(vis[X[1]][Y[1]][0] && vis[X[2]][Y[2]][0] && vis[X[3]][Y[3]][0])){
    Data u=PQ.top();PQ.pop();
    if(vis[u.x][u.y][u.s])continue;
    vis[u.x][u.y][u.s]=1;
    if(u.s){
        for(int i=0;i<5;i++){
            int nx=u.x+dx[i],ny=u.y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m || vis[nx][ny][u.s-1])continue;
            if(u.v<D[nx][ny][u.s-1]){
                D[nx][ny][u.s-1]=u.v;
                PQ.push(Data(u.v,nx,ny,u.s-1));
            }
        }
    }
    else {
        if(D[u.x][u.y][B[u.x][u.y]]>u.v+A[u.x][u.y]){
            D[u.x][u.y][B[u.x][u.y]]=u.v+A[u.x][u.y];
            PQ.push(Data(D[u.x][u.y][B[u.x][u.y]],u.x,u.y,B[u.x][u.y]));
        }
    }
}
}
 
int main(){
freopen("2143.in","r",stdin);
freopen("2143.out","w",stdout);
scanf("%d %d",&n,&m);num=n+m-2;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)scanf("%d",&B[i][j]),B[i][j]=min(B[i][j],max(num-i-j,i+j-2));
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)scanf("%d",&A[i][j]);
}
for(int i=1;i<=3;i++)scanf("%d %d",&X[i],&Y[i]);
Dijkstra(X[1],Y[1]);a1=D[X[2]][Y[2]][0];a2=D[X[3]][Y[3]][0];
Dijkstra(X[2],Y[2]);b1=D[X[1]][Y[1]][0];b2=D[X[3]][Y[3]][0];
Dijkstra(X[3],Y[3]);c1=D[X[1]][Y[1]][0];c2=D[X[2]][Y[2]][0];
if(ans>b1+c1)ans=b1+c1,flag=0;
if(ans>a1+c2)ans=a1+c2,flag=1;
if(ans>a2+b2)ans=a2+b2,flag=2;
if(ans==INF)puts("NO");
else {printf("%c\n%d\n",'X'+flag,ans);}
return 0;
}