| 比赛 |
果蝇王邀请赛div2 |
评测结果 |
AAWWWWWWWWWWWWWWWWWWAWWWWWAWWWWAWWW |
| 题目名称 |
雪王与果蝇王游于濠梁之上 |
最终得分 |
0 |
| 用户昵称 |
rzzakioi |
运行时间 |
15.339 s |
| 代码语言 |
C++ |
内存使用 |
76.21 MiB |
| 提交时间 |
2026-08-27 10:40:46 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
#define pii pair<long long,long long>
using namespace std;
int h,w,a,b,c,n,dis[505][505];
bool vis[505][505],vis2[1275130];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
queue<pair<int,int> >q;
int stx,sty,edx,edy;
signed to[4016030],nxt[4016030],H[4016030],val[4016030];
int dist[1275130],cnt;
void add(int u,int v,int ww){
to[++cnt]=v;
val[cnt]=ww;
nxt[cnt]=H[u];
H[u]=cnt;
}
int num(int s,int x,int y){
return s*(h+1)*(w+1)+x*(w+1)+y;
}
priority_queue<pii,vector<pii>,greater<pii> >pq;
signed main(){
freopen("play.in","r",stdin);
freopen("play.out","w",stdout);
scanf("%lld%lld%lld%lld%lld%lld",&h,&w,&a,&b,&c,&n);
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;i++){
int x,y;
scanf("%lld%lld",&x,&y);
q.push({x,y});
dis[x][y]=0;
if(i==1){
stx=x;sty=y;
}
else if(i==n){
edx=x;edy=y;
}
}
while(!q.empty()){
pair<int,int>u=q.front();
q.pop();
if(vis[u.first][u.second])continue;
vis[u.first][u.second]=1;
for(int i=0;i<4;i++){
int x=u.first+dx[i],y=u.second+dy[i];
if(x<0||x>h||y<0||y>w)continue;
if(dis[u.first][u.second]+1<dis[x][y]){
dis[x][y]=dis[u.first][u.second]+1;
q.push({x,y});
}
}
}
for(int i=0;i<=h;i++){
for(int j=0;j<=w;j++){
if(i>0){
add(num(0,i,j),num(0,i-1,j),c);
add(num(0,i,j),num(1,i-1,j),a+b);
add(num(1,i,j),num(1,i-1,j),a);
}
if(i<h){
add(num(0,i,j),num(0,i+1,j),c);
add(num(0,i,j),num(2,i+1,j),a+b);
add(num(2,i,j),num(2,i+1,j),a);
}
if(j>0){
add(num(0,i,j),num(0,i,j-1),c);
add(num(0,i,j),num(3,i,j-1),a+b);
add(num(3,i,j),num(3,i,j-1),a);
}
if(j<w){
add(num(0,i,j),num(0,i,j+1),c);
add(num(0,i,j),num(4,i,j+1),a+b);
add(num(4,i,j),num(4,i,j+1),a);
}
for(int k=1;k<=4;k++){
add(num(k,i,j),num(0,i,j),c*dis[i][j]);
}
}
}
memset(dist,0x3f,sizeof(dist));
dist[num(0,stx,sty)]=0;
pq.push(make_pair(0,num(0,stx,sty)));
while(!pq.empty()){
int u=pq.top().second;
pq.pop();
if(vis2[u])continue;
vis2[u]=1;
for(int i=H[u];i;i=nxt[i]){
int v=to[i];
if(dist[v]>dist[u]+val[i]){
dist[v]=dist[u]+val[i];
pq.push({dist[v],v});
}
}
}
int ans=0x3f3f3f3f3f3f3f3f;
for(int i=0;i<=4;i++){
ans=min(ans,dist[num(i,edx,edy)]);
}
printf("%lld",ans);
return 0;
}