蒟蒻,代码求调
查看原帖
蒟蒻,代码求调
1140118
wanghaolin44243787楼主2024/7/30 17:49
#include<bits/stdc++.h>
using namespace std;
long long n,m,a,b,c,dis[4][1003][1003],vis[1003][1003],ans=0x7fffffffffffff;
bool va[4][1003][1003];
priority_queue<pair<long long,pair<long long,long long> >,vector<pair<long long,pair<long long,long long> > >,greater<pair<long long,pair<long long,long long> > > >pai[4];
pair<long long,pair<long long,long long> >t,o;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>a>>b>>c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>vis[i][j];
		}
	}
	for(int i=1;i<=3;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=m;k++){
				dis[i][j][k]=0x7fffffffffffff;
			}
		}
	}
	dis[1][n][a]=0;
	dis[2][1][b]=0;
	dis[3][1][c]=0;
	t.first=1;
	t.second.first=n;
	t.second.second=a;
	pai[1].push(t);
	t.second.first=1;
	t.second.second=b;
	pai[2].push(t);
	t.second.first=1;
	t.second.second=c;
	pai[3].push(t);
	for(int i=1;i<=3;i++){
		for(int j=1;j<=n*m;j++){
			t=pai[i].top();
			pai[i].pop();
			while(va[i][t.second.first][t.second.second]&&pai[i].empty()!=0){
				t=pai[i].top();
				pai[i].pop();
			}
			va[i][t.second.first][t.second.second]=1;
			for(int k=-1;k<=1;k++){
				for(int f=-1;f<=1;f++){
					if(k!=0&&f!=0&&t.second.first+k>0&&t.second.first+k<=n&&t.second.second+f>0&&t.second.second+f<=m){
						if(va[i][t.second.first+k][t.second.second+f]==0&&dis[i][t.second.first+k][t.second.second+f]>dis[i][t.second.first][t.second.second]+vis[t.second.first+k][t.second.second+f]){
							dis[i][t.second.first+k][t.second.second+f]=dis[i][t.second.first][t.second.second]+vis[t.second.first+k][t.second.second+f];
							o.first=dis[i][t.second.first+k][t.second.second+f];
							o.second.first=t.second.first+k;
							o.second.second=t.second.second+f;
							pai[i].push(o);
						}
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;i++){
			ans=min(ans,dis[1][i][j]+dis[2][i][j]+dis[3][i][j]);
		}
	}
	cout<<ans;
	return 0;
}
2024/7/30 17:49
加载中...