比赛 果蝇王邀请赛div2 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 雪王与果蝇王游于濠梁之上 最终得分 100
用户昵称 李金泽 运行时间 3.761 s
代码语言 C++ 内存使用 18.32 MiB
提交时间 2026-08-27 12:33:44
显示代码纯文本
#include<bits/stdc++.h>
#define N 100005
#define M 505
#define int long long
#define db double
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int T,n,m,k,A,B,C,sx,sy,tx,ty,d[M][M][5],p[M][M],op,x,y,z,ans,last;
int nx[4]={-1,0,1,0},ny[4]={0,-1,0,1};
const int inf=0x3f3f3f3f3f3f3f3f;
bool vis[M][M];
struct nd{int x,y,k,w;bool operator<(nd y)const{return w>y.w;}};
struct node{int x,y;};
void swap(int &x,int &y){int t=x;x=y;y=t;}
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
void ckmax(int &x,int y){if(y>x)x=y;}
void ckmin(int &x,int y){if(y<x)x=y;}
int fp(int a,int n,int mod){
    int ans=1;
    while(n){
        if(n&1)ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int po(int x){return x*x;}
int sub(int x,int y){return x>y?x-y:y-x;}
int ab(int x){return x<0?-x:x;}
int read(){
    int sum=0;bool f=0;char c=getchar();
    for(;c<48||c>57;c=getchar())if(c==45)f=1;
    for(;c>=48&&c<=57;c=getchar())sum=sum*10+(c&15);
    return f?-sum:sum;
}
int dis(int x1,int y1,int x2,int y2){
    return sub(x1,x2)+sub(y1,y2);
}
void init(){
    memset(p,0x3f,sizeof(p));
    queue<node>q;
    fo(i,0,n)fo(j,0,m)if(vis[i][j])p[i][j]=0,q.push({i,j});
    while(!q.empty()){
        node u=q.front();q.pop();
        fo(k,0,3){
            int tx=u.x+nx[k],ty=u.y+ny[k];
            if(tx<0||ty<0||tx>n||ty>m||p[tx][ty]!=inf)continue;
            p[tx][ty]=p[u.x][u.y]+1;
            q.push({tx,ty});
        }
    }
}
int dijkstra(){
    memset(d,0x3f,sizeof(d));
    priority_queue<nd>q;
    d[sx][sy][4]=0;q.push({sx,sy,4});
    while(!q.empty()){
        nd u=q.top();q.pop();
        if(u.w>d[u.x][u.y][u.k])continue;
        if(u.x==tx&&u.y==ty)return u.w;
        if(u.k<4&&u.w+p[u.x][u.y]*C<d[u.x][u.y][4]){
            d[u.x][u.y][4]=u.w+p[u.x][u.y]*C;
            q.push({u.x,u.y,4,u.w+p[u.x][u.y]*C});
        }
        if(u.k==4)
            fo(k,0,3){
                int tx=u.x+nx[k],ty=u.y+ny[k];
                if(tx<0||ty<0||tx>n||ty>m)continue;
                if(u.w+A+B<d[tx][ty][k]){
                    d[tx][ty][k]=u.w+A+B;
                    q.push({tx,ty,k,u.w+A+B});
                }
                if(u.w+C<d[tx][ty][4]){
                    d[tx][ty][4]=u.w+C;
                    q.push({tx,ty,4,u.w+C});
                }
            }
        else{
            int tx=u.x+nx[u.k],ty=u.y+ny[u.k];
            if(tx<0||ty<0||tx>n||ty>m||u.w+A>=d[tx][ty][u.k])continue;
            d[tx][ty][u.k]=u.w+A;
            q.push({tx,ty,u.k,u.w+A});
        }
    }
    return -1;
}
signed main(){
    freopen("play.in","r",stdin);freopen("play.out","w",stdout);
    n=read();m=read();
    A=read();B=read();C=read();
    z=read();
    fo(i,1,z){
        x=read(),y=read();
        vis[x][y]=1;
        if(i==1)sx=x,sy=y;
        if(i==z)tx=x,ty=y;
    }
    if(A>=C)return !printf("%lld",dis(sx,sy,tx,ty)*C);
    init();
    printf("%lld",dijkstra());
    return 0;
}