比赛 果蝇王邀请赛div2 评测结果 AAWWWWWWWWWWWWWWWWWWAWWWWWAWWWWAWWW
题目名称 雪王与果蝇王游于濠梁之上 最终得分 0
用户昵称 rzzakioi 运行时间 15.339 s
代码语言 C++ 内存使用 76.21 MiB
提交时间 2026-08-27 10:40:46
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
#define pii pair<long long,long long>
using namespace std;
int h,w,a,b,c,n,dis[505][505];
bool vis[505][505],vis2[1275130];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
queue<pair<int,int> >q;
int stx,sty,edx,edy;
signed to[4016030],nxt[4016030],H[4016030],val[4016030];
int dist[1275130],cnt;
void add(int u,int v,int ww){
    to[++cnt]=v;
    val[cnt]=ww;
    nxt[cnt]=H[u];
    H[u]=cnt;
}
int num(int s,int x,int y){
    return s*(h+1)*(w+1)+x*(w+1)+y;
}
priority_queue<pii,vector<pii>,greater<pii> >pq;
signed main(){
    freopen("play.in","r",stdin);
    freopen("play.out","w",stdout);
    scanf("%lld%lld%lld%lld%lld%lld",&h,&w,&a,&b,&c,&n);
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        q.push({x,y});
        dis[x][y]=0;
        if(i==1){
            stx=x;sty=y;
        }
        else if(i==n){
            edx=x;edy=y;
        }
    }
    while(!q.empty()){
        pair<int,int>u=q.front();
        q.pop();
        if(vis[u.first][u.second])continue;
        vis[u.first][u.second]=1;
        for(int i=0;i<4;i++){
            int x=u.first+dx[i],y=u.second+dy[i];
            if(x<0||x>h||y<0||y>w)continue;
            if(dis[u.first][u.second]+1<dis[x][y]){
                dis[x][y]=dis[u.first][u.second]+1;
                q.push({x,y});
            }
        }
    }
    for(int i=0;i<=h;i++){
        for(int j=0;j<=w;j++){
            if(i>0){
                add(num(0,i,j),num(0,i-1,j),c);
                add(num(0,i,j),num(1,i-1,j),a+b);
                add(num(1,i,j),num(1,i-1,j),a);
            }
            if(i<h){
                add(num(0,i,j),num(0,i+1,j),c);
                add(num(0,i,j),num(2,i+1,j),a+b);
                add(num(2,i,j),num(2,i+1,j),a);
            }
            if(j>0){
                add(num(0,i,j),num(0,i,j-1),c);
                add(num(0,i,j),num(3,i,j-1),a+b);
                add(num(3,i,j),num(3,i,j-1),a);
            }
            if(j<w){
                add(num(0,i,j),num(0,i,j+1),c);
                add(num(0,i,j),num(4,i,j+1),a+b);
                add(num(4,i,j),num(4,i,j+1),a);
            }
            for(int k=1;k<=4;k++){
                add(num(k,i,j),num(0,i,j),c*dis[i][j]);
            }
        }
    }
    memset(dist,0x3f,sizeof(dist));
    dist[num(0,stx,sty)]=0;
    pq.push(make_pair(0,num(0,stx,sty)));
    while(!pq.empty()){
        int u=pq.top().second;
        pq.pop();
        if(vis2[u])continue;
        vis2[u]=1;
        for(int i=H[u];i;i=nxt[i]){
            int v=to[i];
            if(dist[v]>dist[u]+val[i]){
                dist[v]=dist[u]+val[i];
                pq.push({dist[v],v});
            }
        }
    }
    int ans=0x3f3f3f3f3f3f3f3f;
    for(int i=0;i<=4;i++){
        ans=min(ans,dist[num(i,edx,edy)]);
    }
    printf("%lld",ans);
    return 0;
}