BZOJ2143: 飞飞侠

佚名 6年前 (2019-04-23) 随笔 1142人围观抢沙发百度已收录

题目大意：大家自己去看题吧。。。解释不清qwq。

题解：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

发现这题是一个经典的最短路题目，但是如果暴力存边好像存不下。。。

那我们就不存边，在最短路转移时直接转移当前点可以到的其他点。

这样理论上复杂度很对，在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;
}