比赛 果蝇王邀请赛div2 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 雪王与果蝇王游于濠梁之上 最终得分 100
用户昵称 郑霁桓 运行时间 18.678 s
代码语言 C++ 内存使用 101.79 MiB
提交时间 2026-08-27 11:18:13
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long n,m,a,b,c,s,x[100005],y[100005],ds[300005],dis[900005];
priority_queue<pair<long long,long long> >pq;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool vs[900005];
struct qq{
    long long x,y;
};
queue<qq>q;
const int N=3e5;
vector<qq>v[900005];
int main(){
    freopen("play.in","r",stdin);
    freopen("play.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>a>>b>>c>>s,n++,m++;
    memset(ds,0x3f,sizeof(ds));
    for(int i=1;i<=s;i++){
        cin>>x[i]>>y[i];
        x[i]++;
        y[i]++;
        q.push({x[i],y[i]});
        ds[(x[i]-1)*m+y[i]]=0;
    }
    while(!q.empty()){
        int xx=q.front().x;
        int yy=q.front().y;
        q.pop();
        for(int i=0;i<4;i++){
            int px=xx+dx[i];
            int py=yy+dy[i];
            if(px<1||py<1||px>n||py>m||ds[(px-1)*m+py]<=1e9) continue;
            ds[(px-1)*m+py]=ds[(xx-1)*m+yy]+1;
            q.push({px,py});
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=2;j<=m;j++){
            int id=(i-1)*m+j;
            v[id].push_back({id-1,c});
            v[id-1].push_back({id,c});
        }
    }
    for(int j=1;j<=m;j++){
        for(int i=2;i<=n;i++){
            int id=(i-1)*m+j;
            v[id].push_back({id-m,c});
            v[id-m].push_back({id,c});
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=2;j<=m;j++){
            int id=(i-1)*m+j;
            v[id+N].push_back({id-1+N,a});
            v[id-1+N].push_back({id+N,a});
        }
    }
    for(int j=1;j<=m;j++){
        for(int i=2;i<=n;i++){
            int id=(i-1)*m+j;
            v[id+N+N].push_back({id-m+N+N,a});
            v[id-m+N+N].push_back({id+N+N,a});
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int id=(i-1)*m+j;
            v[id].push_back({id+N,b});
            v[id+N].push_back({id,ds[id]*c});
            v[id].push_back({id+N+N,b});
            v[id+N+N].push_back({id,ds[id]*c});
        }
    }
    memset(dis,0x3f,sizeof(dis));
    dis[(x[1]-1)*m+y[1]]=0;
    pq.push({0,(x[1]-1)*m+y[1]});
    while(!pq.empty()){
        int tp=pq.top().second;
        pq.pop();
        if(vs[tp]) continue;
        vs[tp]=1;
        for(int i=0;i<v[tp].size();i++){
            if(vs[v[tp][i].x]) continue;
            if(dis[v[tp][i].x]>dis[tp]+v[tp][i].y){
                dis[v[tp][i].x]=dis[tp]+v[tp][i].y;
                pq.push({-dis[v[tp][i].x],v[tp][i].x});
            }
        }
    }
    cout<<dis[(x[s]-1)*m+y[s]];
    return 0;
}