比赛 果蝇王邀请赛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;
}