CE求调(
查看原帖
CE求调(
1072849
Accepetd楼主2025/7/28 10:28
#include<bits/stdc++.h>
#define F(i,a,b) for(register int i=a;i<=b;i=-~i)
#define D(i,a,b) for(register int i=a;i>=b;i=~-i)
#define ad(k) (k=-~k)
#define ll long long
#define min(a,b) (a<b?a:b)
using namespace std;
//char buf[1<<25],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//inline int read(){int x=0,f=1;char c=getchar();for(c;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;for(c;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return x*f;}
const int N=1e4+1;
int n,m,a,b,c,r[N][N];ll dis[3][N][N],mina=LLONG_MAX;bool vis[N][N];
struct node{
	int x,y;ll dis;
	friend bool operator>(const node &a,const node &b){return a.dis<b.dis;}
	friend bool operator<(const node &a,const node &b){return a.dis>b.dis;}
};
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

inline bool check(const int x,const int y){return x<=n&&x>=1&&y<=m&&y>=1;}
inline void dij(const int k,const int nx,const int ny){
	priority_queue<node> q;
	q.push((node){nx,ny,r[nx][ny]});
	memset(vis,0,sizeof vis);
	F(i,1,1000)F(j,1,1000)dis[k][i][j]=LLONG_MAX;
	dis[k][nx][ny]=r[nx][ny];
	while(!q.empty()){
		int x=q.top().x,y=q.top().y;
		q.pop();
		if(vis[x][y])continue;
		vis[x][y]=1;
		F(i,0,3){
			int tx=x+dx[i],ty=y+dy[i];
			if(!check(tx,ty))continue;
			if(dis[k][tx][ty]>dis[k][x][y]+r[tx][ty]){
				dis[k][tx][ty]=dis[k][x][y]+r[tx][ty];
				q.push((node){tx,ty,dis[k][tx][ty]});
			}
		}
	}return;
}

signed main(){
	cin>>n>>m>>a>>b>>c;
	F(i,1,n)F(j,1,m)cin>>r[i][j];
	dij(0,1,a),dij(1,n,b),dij(2,n,c);
	F(i,1,n)F(j,1,m)mina=min(mina,dis[0][i][j]+dis[1][i][j]+dis[2][i][j]-2*r[i][j]);
	cout<<mina;
	return 0;
}
2025/7/28 10:28
加载中...