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