P6833

Aryper · 2021-11-16 22:21:16 · 个人记录

[Cnoi2020]雷雨

真实练习静态查错。。。停课的作用也就这了罢。。。

跑三次单源最短路（就是从那三个点跑），找到最优的分叉点即可。

然后我 Dijkstra 的板子居然都要静态查错，身败名裂。

时间复杂度 O(nm\log nm)。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e3,inf=0x3f3f3f3f3f3f3f3f;

ll n,m,a,b,c,ans;

ll f1[N+5][N+5],f2[N+5][N+5],f3[N+5][N+5],r[N+5][N+5];

ll dx[]={-1,1,0,0},dy[]={0,0,-1,1};

bool vis1[N+5][N+5],vis2[N+5][N+5],vis3[N+5][N+5];

struct node{
    ll x,y,d;
    bool operator > (const node& rhs) const{
        return d>rhs.d;
    }
}t,h;

priority_queue<node,vector<node>,greater<node> > q1,q2,q3;

void Dij() {
    memset(f1,0x3f,sizeof(f1));
    memset(f2,0x3f,sizeof(f2));
    memset(f3,0x3f,sizeof(f3));
    f1[1][a]=r[1][a];f2[n][b]=r[n][b];f3[n][c]=r[n][c];
    t.x=1;t.y=a;t.d=f1[1][a];q1.push(t);
    t.x=n;t.y=b;t.d=f2[n][b];q2.push(t);
    t.x=n;t.y=c;t.d=f3[n][c];q3.push(t);
    while(!q1.empty()) {
        h=q1.top();q1.pop();
        if(vis1[h.x][h.y]) continue;vis1[h.x][h.y]=1;
        for(ll i=0;i<4;i++) {
            ll xx=h.x+dx[i],yy=h.y+dy[i];
            if(xx<=0||xx>n||yy<=0||yy>m) continue;
            if(f1[xx][yy]>f1[h.x][h.y]+r[xx][yy]) {
                f1[xx][yy]=f1[h.x][h.y]+r[xx][yy];
                t.x=xx;t.y=yy;t.d=f1[xx][yy];
                q1.push(t);
            }
        }
    }
    while(!q2.empty()) {
        h=q2.top();q2.pop();
        if(vis2[h.x][h.y]) continue;vis2[h.x][h.y]=1;
        for(ll i=0;i<4;i++) {
            ll xx=h.x+dx[i],yy=h.y+dy[i];
            if(xx<=0||xx>n||yy<=0||yy>m) continue;
            if(f2[xx][yy]>f2[h.x][h.y]+r[xx][yy]) {
                f2[xx][yy]=f2[h.x][h.y]+r[xx][yy];
                t.x=xx;t.y=yy;t.d=f2[xx][yy];
                q2.push(t);
            }
        }
    }
    while(!q3.empty()) {
        h=q3.top();q3.pop();
        if(vis3[h.x][h.y]) continue;vis3[h.x][h.y]=1;
        for(ll i=0;i<4;i++) {
            ll xx=h.x+dx[i],yy=h.y+dy[i];
            if(xx<=0||xx>n||yy<=0||yy>m) continue;
            if(f3[xx][yy]>f3[h.x][h.y]+r[xx][yy]) {
                f3[xx][yy]=f3[h.x][h.y]+r[xx][yy];
                t.x=xx;t.y=yy;t.d=f3[xx][yy];
                q3.push(t);
            }
        }
    }
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    n=read();m=read();a=read();b=read();c=read();

    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=m;j++) {
            r[i][j]=read();
        }
    }

    Dij();

    ans=inf;

    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=m;j++) {
            if(f1[i][j]+f2[i][j]+f3[i][j]-2*r[i][j]<ans) {
                ans=f1[i][j]+f2[i][j]+f3[i][j]-2*r[i][j];
            }
        }
    }

    write(ans);

    return 0;
}