求助
查看原帖
求助
372299
超级玛丽王子楼主2020/9/23 14:55

感觉完全按照题解打的啊

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1005;
const int inf=1e18;
inline int read() {
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    int x=0;
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x;
}
inline int min(int x, int y) {
    return x<y?x:y;
}
struct ver {
    ver() {}
    ver(int _x, int _y, int _z) :x(_x),y(_y),dis(_z) {}
    int x,y,dis;
    bool operator <(const ver b) const {
        return dis>b.dis;
    }
};
int a[maxn][maxn],d[3][maxn][maxn],n=read(),m=read(),A=read(),b=read(),c=read();
signed dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
bitset<maxn>vis[maxn];
inline void dijkstra(int dfn, int cx, int cy) {
    priority_queue<ver, vector<ver> > q;
    q.push(ver(cx,cy,a[cx][cy]));
    for(int i=0;i<1000;i++) vis[i].reset();
    for(int i=1;i<=1000;i++) for(int j=1;j<=1000;j++) d[dfn][i][j]=inf;
    d[dfn][cx][cy]=a[cx][cy];
    while(!q.empty()) {
        int nx=(q.top()).x,ny=q.top().y;
        q.pop();
        if(vis[nx][ny]) continue;
        vis[nx][ny]=1;
        for(int i=0;i<4;i++) {
            int newx=nx+dx[i],newy=ny+dy[i];
            if(newx<1||newx>n||newy<1||newy>m) continue;
            if(d[dfn][newx][newy]>d[dfn][nx][ny]+a[nx][ny]) d[dfn][newx][newy]=d[dfn][nx][ny]+a[nx][ny],q.push(ver(newx,newy,d[dfn][newx][newy]));
        }
    }
}
signed main(void) {
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) a[i][j]=read();
    dijkstra(0,1,A),dijkstra(1,n,b),dijkstra(2,n,c);
    int ans=inf;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            ans=min(ans,d[0][i][j]+d[1][i][j]+d[2][i][j]-2*a[i][j]);
    printf("%lld",ans);
    return 0;
}

是不是bitset锅了?

2020/9/23 14:55
加载中...