5分求调!
查看原帖
5分求调!
541916
RiceFruit楼主2022/7/12 15:12
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define II inline int
#define IV inline void
#define IB inline bool
#define IS inline string
#define IC inline char
const int N=400,S=500,mod=1e9+7;
inline int read();
inline int read(int mod);
int n,m;
int a[N][N];
int b[N][N];
int dx[]={1,-1,0,0,0};
int dy[]={0,0,-1,1,0};
int dh[]={-1,-1,-1,-1,-1};
struct pos{
	int x;
	int y;
}p[4];
struct node{
	pos pas;
	int dis;
	int h;
};
bool operator<(node a,node b){
	if(a.h!=b.h)return a.h>b.h;
	if(a.dis!=b.dis)return a.dis>b.dis;
	if(a.pas.x!=b.pas.x)return a.pas.x>b.pas.x;
	return a.pas.y>b.pas.y;
}
int dis[N][N][N];
bool vis[N][N][N];
void spfa(pos s){
	priority_queue<node>q;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s.x][s.y][0]=0;
	q.push((node){s,0,0});
	while(q.size()){
		node f=q.top();q.pop();
		pos ps=f.pas;int x=ps.x,y=ps.y,h=f.h;
		if(vis[x][y][h])continue;vis[x][y][h]=1;
		if(h==0){
			int tx=x,ty=y,th=h+a[x][y];
			if(dis[tx][ty][th]>dis[x][y][h]+b[x][y]){
				dis[tx][ty][th]=dis[x][y][h]+b[x][y];
				q.push((node){tx,ty,dis[tx][ty][th],th});
			}
		}
		else{
			for(int i=0;i<5;i++){
				int tx=x+dx[i],ty=y+dy[i],th=h+dh[i];
				if(tx<1||tx>n||ty<1||ty>m)continue;
				if(dis[tx][ty][th]>dis[x][y][h]){
					dis[tx][ty][th]=dis[x][y][h];
					q.push((node){tx,ty,dis[tx][ty][th],th});
				}
			}
		}
	}
	return;
}
signed main(){
	n=read(),m=read();
	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],n+m-2);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)b[i][j]=read();
	}
	for(int i=1;i<=3;i++)p[i].x=read(),p[i].y=read();
	int minx=0x3f3f3f3f;char minc='d';
	int mx,my,mz;
	spfa(p[1]);mx=dis[p[2].x][p[2].y][0]+dis[p[3].x][p[3].y][0];
	spfa(p[2]);my=dis[p[1].x][p[1].y][0]+dis[p[3].x][p[3].y][0];
	spfa(p[3]);mz=dis[p[2].x][p[2].y][0]+dis[p[1].x][p[1].y][0];
	if(mx<minx)minx=mx,minc='X';
	if(my<minx)minx=my,minc='Y';
	if(mz<minx)minx=mz,minc='Z';
	if(minc=='d'){
		cout<<"NO";
		return 0;
	}
	cout<<minc<<'\n'<<minx;
	return 0;
}
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<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline int read(int p){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<<1)+(x<<3)+(ch^48);ch=getchar();x=x%p;}return x*f;}

2022/7/12 15:12
加载中...