附上源码：
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #define ll long long #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char ans;int mn=inf; int xx[5]={0,0,1,-1,0},yy[5]={1,-1,0,0,0}; int a1,a2,b1,b2,c1,c2; int n,m,mx; int x1,y1,x2,y2,x3,y3; int a[155][155],b[155][155]; int d[155][155][305]; bool vis[155][155][305]; struct data{int w,x,y,s;}; bool operator>(data a,data b) { return a.w>b.w; } void dij(int x,int y) { priority_queue<data,vector<data>,greater<data> > q; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<=mx;k++) { vis[i][j][k]=0; d[i][j][k]=inf; } vis[x][y][0]=1; d[x][y][a[x][y]]=b[x][y]; q.push((data){b[x][y],x,y,a[x][y]}); while(!q.empty()&&(!vis[x1][y1][0]||!vis[x2][y2][0]||!vis[x3][y3][0])) { int x=q.top().x,y=q.top().y,s=q.top().s;q.pop(); if(vis[x][y][s])continue;vis[x][y][s]=1; if(s>0) { for(int k=0;k<5;k++) { int nowx=x+xx[k],nowy=y+yy[k]; if(nowx<1||nowy<1||nowx>n||nowy>m||vis[nowx][nowy][s-1])continue; if(d[x][y][s]<d[nowx][nowy][s-1]) { d[nowx][nowy][s-1]=d[x][y][s]; q.push((data){d[nowx][nowy][s-1],nowx,nowy,s-1}); } } } else { int t=a[x][y]; if(d[x][y][t]>d[x][y][0]+b[x][y]) { d[x][y][t]=d[x][y][0]+b[x][y]; q.push((data){d[x][y][t],x,y,t}); } } } while(!q.empty())q.pop(); } int main() { freopen("10.in","r",stdin); freopen("10.out","w",stdout); n=read();m=read();mx=n+m-2; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a[i][j]=read(); a[i][j]=min(a[i][j],max(mx-i-j,i+j-2)); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) b[i][j]=read(); x1=read();y1=read();x2=read();y2=read();x3=read();y3=read(); dij(x1,y1);a1=d[x2][y2][0];a2=d[x3][y3][0]; dij(x2,y2);b1=d[x1][y1][0];b2=d[x3][y3][0]; dij(x3,y3);c1=d[x1][y1][0];c2=d[x2][y2][0]; if(b1+c1<mn)mn=b1+c1,ans='X'; if(a1+c2<mn)mn=a1+c2,ans='Y'; if(a2+b2<mn)mn=a2+b2,ans='Z'; if(mn==inf)puts("NO"); else { printf("%c\n",ans); printf("%d\n",mn); } return 0; }
