想知道如何将最短路改进优化,玄关
查看原帖
想知道如何将最短路改进优化,玄关
656447
__Ship_楼主2025/7/20 08:41
#include<bits/stdc++.h>

using namespace std;
#define int long long
int n,m,h[5050][5050],tf[5050][5050],k,ans=0,vis[5050][5050]; 
int fx[5]={0,1,0,-1,0};
int fy[5]={0,0,1,0,-1};
struct node{
	int x,y,step;
	bool operator <(const node &b) const{
		return step < b.step;
	}
};
priority_queue<node> q;
void bfs(){
	while(!q.empty()){
		node f=q.top();
		q.pop();
		
		for(int i = 1 ; i <= 4 ; i++){
			int tx=f.x+fx[i],ty=f.y+fy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&vis[tx][ty]>max(f.step,abs(h[tx][ty]-h[f.x][f.y]))){
				vis[tx][ty]=max(f.step,abs(h[tx][ty]-h[f.x][f.y]));
				q.push({tx,ty,max(f.step,abs(h[tx][ty]-h[f.x][f.y]))});
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			cin>>h[i][j];
			vis[i][j]=1e18;
		}
	}
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			cin>>tf[i][j];
			if(tf[i][j]&&!k){
				q.push({i,j,0});
				k=1;	
			}
		}
	}
	bfs();
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			if(tf[i][j]){
//				cout<<vis[i][j]<<" ";
				ans=max(vis[i][j],ans);
			}
		} 
	}
	cout<<ans;
	return 0;
}
2025/7/20 08:41
加载中...