| 比赛 |
果蝇王邀请赛div2 |
评测结果 |
AAAAATTAAATTTTATTATWATTTTTTTTTTTTTT |
| 题目名称 |
雪王与果蝇王游于濠梁之上 |
最终得分 |
5 |
| 用户昵称 |
dream |
运行时间 |
29.646 s |
| 代码语言 |
C++ |
内存使用 |
24.36 MiB |
| 提交时间 |
2026-08-27 12:27:45 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> PI;
const int M=505,N=100005;
const int NN=M*M;
int h,w,n;
ll a,b,c,ans;
struct node{
int x,y;
}z[N];
ll throwm(ll x,ll y){
return abs(x-y)*a+b;
}
ll walk(ll x,ll y){
return abs(x-y)*c;
}
int nearest[M][M];
struct bbase{
int x,y,s;
};
int vis[M][M];
int xy[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
queue<bbase> qq;
void bfs(){
while(qq.size()){
bbase t=qq.front();
qq.pop();
nearest[t.x][t.y]=t.s;
for(int i=0;i<4;i++){
int xx=t.x+xy[i][0],yy=t.y+xy[i][1];
if(xx<0||yy<0||xx>h||yy>w||vis[xx][yy]) continue;
vis[xx][yy]=1;
qq.push({xx,yy,t.s+1});
}
}
}
int getbh(int x,int y){
return x*(w+1)+y;
}
node getxy(int bh){
return (node){bh/(w+1),bh%(w+1)};
}
ll dis[NN];
int mk[NN];
priority_queue<PI,vector<PI>,greater<PI>> q;
int mnx,mny,mxx,mxy;
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
int bh1=getbh(z[1].x,z[1].y);
dis[bh1]=0;
q.push({0,bh1});
while(q.size()){
PI t=q.top();
q.pop();
int u=t.second;
if(mk[u]) continue;
mk[u]=1;
node uz=getxy(u);
for(int i=mnx;i<=mxx;i++){ //i,y
if(uz.x==i) continue;
int bh=getbh(i,uz.y);
ll tmp=min(throwm(uz.x,i)+nearest[i][uz.y]*1ll*c,walk(uz.x,i))+dis[u];
if(tmp<dis[bh]){
dis[bh]=tmp;
q.push({dis[bh],bh});
}
}
for(int i=mny;i<=mxy;i++){ //x,i
if(uz.y==i) continue;
int bh=getbh(uz.x,i);
ll tmp=min(throwm(uz.y,i)+nearest[uz.x][i]*1ll*c,walk(uz.y,i))+dis[u];
if(tmp<dis[bh]){
dis[bh]=tmp;
q.push({dis[bh],bh});
}
}
}
}
int main(){
freopen("play.in","r",stdin);
freopen("play.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>h>>w;
cin>>a>>b>>c;
cin>>n;
for(int i=1;i<=n;i++){
cin>>z[i].x>>z[i].y;
qq.push({z[i].x,z[i].y,0});
vis[z[i].x][z[i].y]=1;
}
mnx=mny=0,mxx=h,mxy=w;
if(n<=2){
ans=min(throwm(z[1].x,z[n].x)+walk(z[1].y,z[n].y),throwm(z[1].y,z[n].y)+walk(z[1].x,z[n].x));
ans=min(ans,walk(z[1].x,z[n].x)+walk(z[1].y,z[n].y));
}
else{
bfs();
dijkstra();
ans=dis[getbh(z[n].x,z[n].y)];
}
cout<<ans;
return 0;
}