题解

本题使用分层图最短路求解带状态的路径问题。

算法思路：

1. 问题建模：

   • 足球可以在三种状态下移动：正常移动（代价 $c$）、横向加速（代价 $a$）、纵向加速（代价 $a$）
   • 使用分层图表示不同的移动状态
   • 建立三层图：第 0 层为正常状态，第 1 层为横向加速状态，第 2 层为纵向加速状态

2. 预处理距离：

   • 使用 BFS 预处理每个格子到最近的球员的距离 $d[i][j]$
   • 从所有球员位置开始多源 BFS，向外扩散
   • $d[i][j]$ 表示该格子到最近球员的曼哈顿距离

3. 图的构建：

   • 正常层 $\to$ 加速层：代价为 $b$（切换到加速状态）
   • 加速层 $\to$ 正常层：代价为 $d[i][j] \times c$（恢复到正常状态）
   • 相邻格子：
     • 正常层之间：代价 $c$
     • 横向加速层之间（横向移动）：代价 $a$
     • 纵向加速层之间（纵向移动）：代价 $a$

4. 最短路求解：

   • 使用 Dijkstra 算法求从第一个球员位置到最后一个球员位置的最短路
   • 状态总数为 $3 \times h \times w$

时间复杂度：$O(hw \log(hw))$

// -O2 -Wall -Wextra -Wl,--stack=100000000
// -fsanitize=address,undefined -Wall -Wextra
//https://www.microsoft.com/zh-cn/download/details.aspx?id=35
#include<bits/stdc++.h>
#define int long long
#define spc() ALL_OUT[++ALL_LEN]=' '
#define nxtl() ALL_OUT[++ALL_LEN]='\n'
#define clrout() ALL_OUT[ALL_LEN+1]=0,fputs(ALL_OUT,stdout),ALL_LEN=-1
#define rt() return clrout(),0;
using namespace std;
char OUT_LIST[41],ALL_OUT[100100];
int ALL_LEN=-1;
void write(int x,short l=40){
    const int k=x/10;
	OUT_LIST[l]=(x-(k<<1)-(k<<3))|'0';
    if(x>9)write(k,l-1);
    else{
    	if(ALL_LEN>100000)clrout();
    	for(;l<33;l+=8){
    		ALL_OUT[1+ALL_LEN]=OUT_LIST[l];
    		ALL_OUT[2+ALL_LEN]=OUT_LIST[l+1];
    		ALL_OUT[3+ALL_LEN]=OUT_LIST[l+2];
    		ALL_OUT[4+ALL_LEN]=OUT_LIST[l+3];
    		ALL_OUT[5+ALL_LEN]=OUT_LIST[l+4];
    		ALL_OUT[6+ALL_LEN]=OUT_LIST[l+5];
    		ALL_OUT[7+ALL_LEN]=OUT_LIST[l+6];
    		ALL_OUT[ALL_LEN=(8+ALL_LEN)]=OUT_LIST[l+7];
		}
		switch(40-l){
			case 7:ALL_OUT[++ALL_LEN]=OUT_LIST[l++];
			case 6:ALL_OUT[++ALL_LEN]=OUT_LIST[l++];
			case 5:ALL_OUT[++ALL_LEN]=OUT_LIST[l++];
			case 4:ALL_OUT[++ALL_LEN]=OUT_LIST[l++];
			case 3:ALL_OUT[++ALL_LEN]=OUT_LIST[l++];
			case 2:ALL_OUT[++ALL_LEN]=OUT_LIST[l++];
			case 1:ALL_OUT[++ALL_LEN]=OUT_LIST[l++];
			case 0:ALL_OUT[++ALL_LEN]=OUT_LIST[l++];
		}
	}
}
#define xxx const int mid=(l+r)>>1
int read(){
   char ch=getchar();
   int s=0;
   while(ch<'0'||ch>'9')ch=getchar();
   while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
   return s;
}
inline int gcd(int a,int b){
	int az=__builtin_ctzll(a),bz=__builtin_ctzll(b),d;
	const int tmp=min(az,bz);
	b>>=bz;
	while(a)az=__builtin_ctzll(d=b-(a>>=az)),((a<b)?(b=a):0),a=(d>0?d:-d);
	return b<<tmp;
}
#define dian(i,j) ((i-1)*w+j)
const int N=2e6+10;
vector<pair<int,int>>G[N];
int d[505][505],f[N],vis[N],n,h,w,a,b,c;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
signed main(){
	memset(d,0x3f,sizeof(d));
    cin>>h>>w; 
    ++h,++w;
    cin>>a>>b>>c;
    cin>>n;
	memset(f,0x3f,sizeof(f));
    int s,t;
	for(int i=1;i<=n;i++){
		cin>>s>>t;
		d[++s][++t]=0;
		if(i==1)f[dian(s,t)]=0,q.push({0,dian(s,t)});
	}
	for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)d[i+1][j]=min(d[i][j]+1,d[i+1][j]),d[i][j+1]=min(d[i][j]+1,d[i][j+1]);
	for(int i=h;i>=1;i--)for(int j=w;j>=1;j--)d[i-1][j]=min(d[i][j]+1,d[i-1][j]),d[i][j-1]=min(d[i][j]+1,d[i][j-1]);
	for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)G[dian(i,j)+h*w].push_back(make_pair(dian(i,j),d[i][j]*c)),G[dian(i,j)+2*h*w].push_back(make_pair(dian(i,j),d[i][j]*c)),G[dian(i,j)].push_back(make_pair(dian(i,j)+h*w,b)),G[dian(i,j)].push_back(make_pair(dian(i,j)+2*h*w,b));
	for(int i=1;i<=h;i++)for(int j=1;j<w;j++)G[dian(i,j)].push_back(make_pair(dian(i,j+1),c)),G[dian(i,j+1)].push_back(make_pair(dian(i,j),c)),G[dian(i,j)+h*w].push_back(make_pair(dian(i,j+1)+h*w,a)),G[dian(i,j+1)+h*w].push_back(make_pair(dian(i,j)+h*w,a));
	for(int i=1;i<h;i++)for(int j=1;j<=w;j++)G[dian(i,j)].push_back(make_pair(dian(i+1,j),c)),G[dian(i+1,j)].push_back(make_pair(dian(i,j),c)),G[dian(i,j)+2*h*w].push_back(make_pair(dian(i+1,j)+2*h*w,a)),G[dian(i+1,j)+2*h*w].push_back(make_pair(dian(i,j)+2*h*w,a));
	while(!q.empty()){
		int u=q.top().second;
        q.pop();
		if(vis[u])continue;
        vis[u]=1;
		for(auto[v,w]:G[u])if(f[v]>f[u]+w)q.push({(f[v]=f[u]+w),v});
	}
	cout<<f[dian(s,t)];
	return 0;
}