洛谷上CE,本地编译能过
查看原帖
洛谷上CE,本地编译能过
688247
liyihan1025楼主2023/9/27 22:20

RT,本地没报错没报警告

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;
int n,m;
int a[N][N],disa[N][N],disb[N][N],disc[N][N];
struct mapp{
	int x,y;
	friend operator>(const mapp &A,const mapp &B){
		return a[A.x][A.y]>a[B.x][B.y];
	}
};
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
bool insz(int x,int y){
	return x>=1&&x<=n&&y>=1&&y<=m;
}
void setval(int typ,int x,int y,int val){
	if(typ==1) disa[x][y]=val;
	if(typ==2) disb[x][y]=val;
	if(typ==3) disc[x][y]=val;
	return;
}
void plu(int typ,int x,int y,int val){
	if(typ==1) disa[x][y]+=val;
	if(typ==2) disb[x][y]+=val;
	if(typ==3) disc[x][y]+=val;
	return;
}
int gettyp(int typ,int x,int y){
	if(typ==1) return disa[x][y];
	if(typ==2) return disb[x][y];
	if(typ==3) return disc[x][y];
}
void dijkstra(int sx,int sy,int typ){
	priority_queue<mapp,vector<mapp>,greater<mapp> > pq;
	pq.push({sx,sy});
	setval(typ,sx,sy,a[sx][sy]);
	while(!pq.empty()){
		mapp cur=pq.top();pq.pop();
		for(int i=0;i<4;i++){
			int nx=cur.x+dx[i],ny=cur.y+dy[i];
			if(insz(nx,ny)&&gettyp(typ,nx,ny)>gettyp(typ,cur.x,cur.y)+a[nx][ny]){
				if(gettyp(typ,nx,ny)==1e18)
					setval(typ,nx,ny,gettyp(typ,cur.x,cur.y)+a[nx][ny]);
				else
					plu(typ,nx,ny,gettyp(typ,cur.x,cur.y)+a[nx][ny]);
				pq.push({nx,ny});
			}
		}
	}
	return;
}
signed main(){
	int A,B,C;
	cin>>n>>m>>A>>B>>C;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			disa[i][j]=disb[i][j]=disc[i][j]=1e18;
		}
	}
	dijkstra(1,A,1);
	dijkstra(n,B,2);
	dijkstra(n,C,3);
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<disa[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	int mins=1e18;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			mins=min(mins,disa[i][j]+disb[i][j]+disc[i][j]-2*a[i][j]);
		}
	}
	cout<<mins;
	return 0;
}
2023/9/27 22:20
加载中...