30pts 求调
查看原帖
30pts 求调
1121995
2021zjhs005楼主2024/3/18 20:38

rt,WA on #6,9。

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rrep(i,x,y) for(int i=x;i>=y;i--)
#define sc scanf
#define pr printf
inline int read(){int s=0,w=1;char c=getchar();while(!isdigit(c)){if(c=='-') w=-1;c=getchar();}while(isdigit(c)){s=(s<<1)+(s<<3)+(c^48);c=getchar();}return s*w;}

const int N=1005;
int n,m,a,b,c,ans=INT_MAX,aa[N][N],dis[3][N][N];
bool vis[N][N];
const int fx[4]={0,0,1,-1},fy[4]={1,-1,0,0};

struct point{
  int x,y,w;
  bool operator < (const point &a) const{
    return w>a.w;
  }
};

inline void bfs(int lazy,int sx,int sy){
  priority_queue <point> q;
  memset(vis,0,sizeof vis);
  memset(dis[lazy], 0x3f3f3f3f, sizeof (dis[lazy]));
   dis[lazy][sx][sy]=aa[sx][sy];
  q.push((point){sx,sy,dis[lazy][sx][sy]});
  while(!q.empty()){
    int nowx=q.top().x,nowy=q.top().y;
    q.pop();
    if(vis[nowx][nowy]) continue;
    vis[nowx][nowy]=1;
    rep(i,0,3){
      int ax=nowx+fx[i],ay=nowy+fy[i];
      if(ax<1||ax>n||ay<1||ay>m) continue;
      if(dis[lazy][ax][ay]>dis[lazy][nowx][nowy]+aa[ax][ay]){
         dis[lazy][ax][ay]=dis[lazy][nowx][nowy]+aa[ax][ay];
         q.push((point){ax,ay,dis[lazy][ax][ay]});
      }
    }
  }
}

signed main(){
  n=read();m=read();a=read();b=read();c=read();
  rep(i,1,n)
    rep(j,1,m) cin>>aa[i][j];
  bfs(0,1,a);bfs(1,n,b);bfs(2,n,c);
  rep(i,1,n)
    rep(j,1,m) {//cout<<dis[0][i][j]<<" "<<dis[1][i][j]<<" "<<dis[2][i][j]<<endl;
    ans=min(ans,dis[0][i][j]+dis[1][i][j]+dis[2][i][j]-2*aa[i][j]);//cout<<ans<<endl;
    }
  return pr("%lld\n",ans),0;
}
2024/3/18 20:38
加载中...