比赛 果蝇王邀请赛div2 评测结果 AAAAAAAAAAAAAAAAAAAATAAAAATAAAAAAAW
题目名称 雪王与果蝇王游于濠梁之上 最终得分 35
用户昵称 2_16鸡扒拌面 运行时间 21.675 s
代码语言 C++ 内存使用 28.07 MiB
提交时间 2026-08-27 12:03:48
显示代码纯文本
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define SNSNMO 510
using namespace std;
const ll INF=4e18;

int H,W,n;
ll A,B,C;
ll d0[SNSNMO][SNSNMO],d1[SNSNMO][SNSNMO],near[SNSNMO][SNSNMO];
int sx,sy,ex,ey;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct Node{
	ll d;
	int x,y;
	bool operator>(const Node& o)const
	{
		return d>o.d;
	}
};
priority_queue<Node,vector<Node>,greater<Node> > pq;
queue<pair<int,int> > q;

int main()
{
	freopen("play.in","r",stdin);
	freopen("play.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin>>H>>W;
	cin>>A>>B>>C;
	cin>>n;
	vector<pair<int,int> > p;
	for(int i=0;i<n;++i)
	{
		int s,t;
		cin>>s>>t;
		p.push_back({s,t});
		if(i==0)
		{
			sx=s;
			sy=t;
		}
		if(i==n-1)
		{
			ex=s;
			ey=t;
		}
	}
	for(int i=0;i<=H;++i)
		for(int j=0;j<=W;++j)
			near[i][j]=INF;
	for(auto &x:p)
	{
		near[x.first][x.second]=0;
		q.push(x);
	}
	while(!q.empty())
	{
		auto [x,y]=q.front();
		q.pop();
		for(int k=0;k<4;++k)
		{
			int nx=x+dx[k],ny=y+dy[k];
			if(nx<0||nx>H||ny<0||ny>W) continue;
			if(near[nx][ny]>near[x][y]+1)
			{
				near[nx][ny]=near[x][y]+1;
				q.push({nx,ny});
			}
		}
	}
	for(int i=0;i<=H;++i)
		for(int j=0;j<=W;++j)
			d0[i][j]=d1[i][j]=INF;
	d0[sx][sy]=0;
	pq.push({0,sx,sy});
	while(!pq.empty())
	{
		auto [d,x,y]=pq.top();
		pq.pop();
		if(d>d0[x][y]&&d>d1[x][y]) continue;
		if(d==d0[x][y])
		{
			for(int k=0;k<4;++k)
			{
				int nx=x+dx[k],ny=y+dy[k];
				if(nx<0||nx>H||ny<0||ny>W) continue;
				if(d0[nx][ny]>d+C)
				{
					d0[nx][ny]=d+C;
					pq.push({d0[nx][ny],nx,ny});
				}
			}
			for(int ny=0;ny<=W;++ny)
			{
				if(ny==y) continue;
				ll c=d+A*abs(ny-y)+B;
				if(d1[x][ny]>c)
				{
					d1[x][ny]=c;
					pq.push({d1[x][ny],x,ny});
				}
			}
			for(int nx=0;nx<=H;nx++)
			{
				if(nx==x) continue;
				ll c=d+A*abs(nx-x)+B;
				if(d1[nx][y]>c)
				{
					d1[nx][y]=c;
					pq.push({d1[nx][y],nx,y});
				}
			}
		}
		if(d==d1[x][y])
		{
			if(near[x][y]<INF)
			{
				ll c=d+C*near[x][y];
				if(d0[x][y]>c)
				{
					d0[x][y]=c;
					pq.push({d0[x][y],x,y});
				}
			}
		}
	}
	cout<<d0[ex][ey];
	return 0;
}