欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ2143: 飞飞侠

程序员文章站 2022-05-22 13:35:21
...

题目大意:大家自己去看题吧。。。解释不清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;
}