ABC384 E - Takahashi is Slime 2

封面

思路：

从一个点出发前往其它点，要求必须到达点的强度严格小于我们的强度的 1X\dfrac{1}{X} 倍，每次都可以从我们走过的地方形成的多边形的边上向没有到过的地方。

考虑 bfs。

与 bfs 模版不同的地方就在于每次都可以从我们走过的地方形成的多边形的边上向没有到过的地方，由此可以使用堆进行处理，每次把在边的旁边的点放进堆，每次取力量最小的点走。
如果这时要走到点的强度已经不严格小于现在的强度的 1X\dfrac{1}{X} 倍了，那么可以直接输出现在的值，然后结束程序。
可以这样的原因是我们采用了堆并且每次取的的最小强度，那么现在最小强度已经不严格小于现在的强度的 1X\dfrac{1}{X} 倍了，后面的强度只会大于或等于最小强度，所以也会是相同的结果，所以可以直接结束。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int H,W,p,q,x;
LL s[510][510];
bool bj[510][510];
struct node{
	LL x,y,v;
	friend bool operator <(node x,node y){
		return x.v>y.v;
	}
};
LL now;
priority_queue<node>dl;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int main(){
	cin>>H>>W>>x>>p>>q;
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			cin>>s[i][j];
		}
	}
	now=0;
	bj[p][q]=1;
	bool bjj=0;
	dl.push({p,q,s[p][q]});
	while(dl.empty()==0){
		node tamp=dl.top();dl.pop();
//		cout<<tamp.x<<" "<<tamp.y<<"\n";
		if(bjj&&1.00000*now/x<=tamp.v)break;
		now+=tamp.v;
		bjj=1;
		for(int i=0;i<4;i++){
			int tx=dx[i]+tamp.x,ty=dy[i]+tamp.y;
			if(tx>=1&&ty>=1&&tx<=H&&ty<=W&&!bj[tx][ty]){
				bj[tx][ty]=1;
				dl.push({tx,ty,s[tx][ty]});
			}
		}
	}
	
	cout<<now;
	return 0;
}

AC 记录。