社区讨论

0分求调!!!

P6833[Cnoi2020] 雷雨参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mdigiwf2
此快照首次捕获于
2025/07/25 14:45
7 个月前
此快照最后确认于
2025/11/04 03:45
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1005,M=1e18;
struct node{
	ll x,y,dis;
	bool operator <(const node &b)const{
		return dis>b.dis;
	}
};
ll n,m,a,b,c,r[N][N],dis[4][N][N],vis[N][N],ans=1e18;
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
void dij(ll k,ll sx,ll sy){
	memset(vis,0,sizeof(vis));
	priority_queue<node> q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dis[k][i][j]=M;
		}
	}
	q.push({sx,sy,r[sx][sy]});
	dis[k][sx][sy]=r[sx][sy];
	while(q.size()){
		int fx=q.top().x,fy=q.top().y;
		q.pop();
		if(vis[fx][fy]) continue;
		vis[fx][fy]=1;
		for(int i=0;i<4;i++){
			int nx=fx+dx[i],ny=fy+dy[i];
			if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
			if(dis[k][nx][ny]>dis[k][fx][fy]+r[nx][ny]){
				dis[k][nx][ny]=dis[k][fx][fy]+r[nx][ny];
				q.push({nx,ny});
			}
		}
	}
	
}
int main(){
	cin>>n>>m>>a>>b>>c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>r[i][j];
		}
	}
	dij(1,n,a);
	dij(2,1,b);
	dij(3,1,c);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ans=min(ans,dis[1][i][j]+dis[2][i][j]+dis[3][i][j]-2*r[i][j]);
		}
	}
	cout<<ans;
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...