为什么不能用优先队列bfs?
查看原帖
为什么不能用优先队列bfs?
536337
eb0ycn楼主2024/4/7 12:25

到某个格子,肯定是能量越多越好啊……为啥wa3?

还有,在AT上只有WA,在洛谷上就RE

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int h,w,n,r,c,e,mp[201][201],sx,sy,ex,ey,nx,ny,ne,dis[201][201];
char op;
struct node{
	int x,y,now;
	bool operator<(const node&cwx)const{return now<cwx.now;}
}le;
priority_queue<node>q;
bool vis[201][201];
int main(){
	scanf("%d%d",&h,&w);
	for(int i=1;i<=h;++i){
		getchar();
		for(int j=1;j<=w;++j){
			op=getchar(),dis[i][j]=-1;
			if(op=='S')sx=i,sy=j;
			if(op=='T')ex=i,ey=j;
			if(op=='#')mp[i][j]=1000000;
		}
	}
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d%d%d",&r,&c,&e),mp[r][c]=max(e,0);
	q.push({sx,sy,mp[sx][sy]}),dis[sx][sy]=mp[sx][sy];
	while(!q.empty()){
		le=q.top(),r=le.x,c=le.y,e=le.now,q.pop();
		if(vis[r][c])continue;vis[r][c]=1;
		if(!e)continue;
		for(int i=0;i<4;++i){
			nx=r+dx[i],ny=c+dy[i],ne=max(mp[nx][ny],e-1);
			if(!nx||!ny||nx>h||ny>w||mp[nx][ny]==1000000)continue;
			if(ne>dis[nx][ny])q.push({nx,ny,ne}),dis[nx][ny]=ne;
		}
	}return 0&printf("%s",vis[ex][ey]?"Yes":"No");
}
2024/4/7 12:25
加载中...