比赛 果蝇王邀请赛div2 评测结果 AAWWWWWWWWWAAWAWWWAWWWWWEEEEEEWEWWE
题目名称 雪王与果蝇王游于濠梁之上 最终得分 0
用户昵称 exil 运行时间 1.991 s
代码语言 C++ 内存使用 13.44 MiB
提交时间 2026-08-27 12:29:35
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
int tu[2510][2510];
int p[5010];
int cnt;
int xx[2510],yy[2510];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
int dis[2510];
int qi,zhong,n;
void disl(){
    for(int i = 1;i<=cnt;i++){
        dis[i]=INT_MAX;
    }
    dis[qi]=0;
    q.push({0,qi});
    while(!q.empty()){
        int re=q.top().first;
        int d=q.top().second;
        q.pop();
        for(int i = 1;i<=n;i++){
            if(i==qi)continue;
            if(dis[i]>re+tu[d][i]){
                dis[i]=re+tu[d][i];
                q.push({dis[i],i});
            }
        }  
    }
    cout<<dis[zhong];
}
signed main(){
    freopen("play.in","r",stdin);
    freopen("play.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int h,w;
    cin>>h>>w;
    h++;
    w++;
    int a,b,c;
    cin>>a>>b>>c;
    cin>>n;
    set<int>ss;
    for(int i = 1;i<=n;i++){
        int s,t;
        cin>>s>>t;
        
        s++;
        t++;
        int we=ss.size();
        ss.insert(s*7821+t*998244353);
        if(ss.size()>we){
            cnt++;
            xx[cnt]=s;
            yy[cnt]=t;
            //cout<<ss.size()<<endl; 
        }
        
        
        if(i==1)qi=cnt;
        if(i==n)zhong=cnt;
    }
//    if(a>c || b>c){
//        cout<<(abs(xx[zhong]-xx[qi])+abs(yy[qi]-yy[zhong]))*c;
//        return 0;
//    }
    for(int i = 1;i<=505;i++){
        p[i]=min(a*i+b,c*i);
    }
    for(int i = 1;i<=cnt;i++){
        for(int j = 1;j<=cnt;j++){
            if(i==j)continue;
            tu[i][j]=min(abs(xx[i]-xx[j]),abs(yy[i]-yy[j]))*c+p[max(abs(xx[i]-xx[j]),abs(yy[i]-yy[j]))];
            
            //cout<<i<<" "<<j<<" "<<tu[i][j]<<endl;
        }
    }
    disl();
    
    return 0;
}