题目大意:大家自己去看题吧。。。解释不清qwq。
题解:
发现这题是一个经典的最短路题目,但是如果暴力存边好像存不下。。。
那我们就不存边,在最短路转移时直接转移当前点可以到的其他点。
这样理论上复杂度很对,在BZOJ和洛谷都过了,但是被FZOJ卡成了60分,听说要把堆优化Dijkstra改成线段树优化Dijkstra。。。
太懒了不想改,细节大家看代码吧。。。
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
int a[155][155],b[155][155],n,m,d[155][155],xx[5],yy[5],dis[5],ans,id,p[5][5];
int abs(int p){
if (p<0) return -p;
return p;
}
struct HeapNode{
int x,y,d;
bool operator<(const HeapNode& rhs) const{
return d>rhs.d;
}
};
void Dijkstra(int k){
priority_queue<HeapNode> q;
memset (d,0x3f3f3f3f,sizeof (d));
d[xx[k]][yy[k]]=0;
q.push((HeapNode){xx[k],yy[k],0});
while (!q.empty()){
HeapNode u=q.top();q.pop();
if (d[u.x][u.y]!=u.d) continue;
int len=b[u.x][u.y],f=a[u.x][u.y]+d[u.x][u.y];
for (register int i=max(1,u.x-len);i<=min(n,u.x+len);++i){
int tmp=len-abs(u.x-i);
for (register int j=max(1,u.y-tmp);j<=min(m,u.y+tmp);++j){
if (d[i][j]>f){
d[i][j]=f;
q.push((HeapNode){i,j,d[i][j]});
}
}
}
}
for (register int i=1;i<=3;++i){
p[k][i]=d[xx[i]][yy[i]];
}
}
int main(){
scanf ("%d%d",&n,&m);
for (register int i=1;i<=n;++i){
for (register int j=1;j<=m;++j){
scanf ("%d",&b[i][j]);
}
}
for (register int i=1;i<=n;++i){
for (register int j=1;j<=m;++j){
scanf ("%d",&a[i][j]);
}
}
for (register int i=1;i<=3;++i){
scanf ("%d%d",&xx[i],&yy[i]);
}
for (register int i=1;i<=3;++i){
Dijkstra(i);
}
id=0;ans=0x3f3f3f3f;
for (register int i=1;i<=3;++i){
if (p[1][i]+p[2][i]+p[3][i]<ans){
id=i;ans=p[1][i]+p[2][i]+p[3][i];
}
}
if (ans==0x3f3f3f3f){
printf ("NO\n");
}
else{
if (id==1){
printf ("X\n");
}
if (id==2){
printf ("Y\n");
}
if (id==3){
printf ("Z\n");
}
printf ("%d\n",ans);
}
return 0;
}