| 比赛 |
果蝇王邀请赛div2 |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
雪王与果蝇王游于濠梁之上 |
最终得分 |
100 |
| 用户昵称 |
郑霁桓 |
运行时间 |
18.678 s |
| 代码语言 |
C++ |
内存使用 |
101.79 MiB |
| 提交时间 |
2026-08-27 11:18:13 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long n,m,a,b,c,s,x[100005],y[100005],ds[300005],dis[900005];
priority_queue<pair<long long,long long> >pq;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool vs[900005];
struct qq{
long long x,y;
};
queue<qq>q;
const int N=3e5;
vector<qq>v[900005];
int main(){
freopen("play.in","r",stdin);
freopen("play.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>a>>b>>c>>s,n++,m++;
memset(ds,0x3f,sizeof(ds));
for(int i=1;i<=s;i++){
cin>>x[i]>>y[i];
x[i]++;
y[i]++;
q.push({x[i],y[i]});
ds[(x[i]-1)*m+y[i]]=0;
}
while(!q.empty()){
int xx=q.front().x;
int yy=q.front().y;
q.pop();
for(int i=0;i<4;i++){
int px=xx+dx[i];
int py=yy+dy[i];
if(px<1||py<1||px>n||py>m||ds[(px-1)*m+py]<=1e9) continue;
ds[(px-1)*m+py]=ds[(xx-1)*m+yy]+1;
q.push({px,py});
}
}
for(int i=1;i<=n;i++){
for(int j=2;j<=m;j++){
int id=(i-1)*m+j;
v[id].push_back({id-1,c});
v[id-1].push_back({id,c});
}
}
for(int j=1;j<=m;j++){
for(int i=2;i<=n;i++){
int id=(i-1)*m+j;
v[id].push_back({id-m,c});
v[id-m].push_back({id,c});
}
}
for(int i=1;i<=n;i++){
for(int j=2;j<=m;j++){
int id=(i-1)*m+j;
v[id+N].push_back({id-1+N,a});
v[id-1+N].push_back({id+N,a});
}
}
for(int j=1;j<=m;j++){
for(int i=2;i<=n;i++){
int id=(i-1)*m+j;
v[id+N+N].push_back({id-m+N+N,a});
v[id-m+N+N].push_back({id+N+N,a});
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int id=(i-1)*m+j;
v[id].push_back({id+N,b});
v[id+N].push_back({id,ds[id]*c});
v[id].push_back({id+N+N,b});
v[id+N+N].push_back({id,ds[id]*c});
}
}
memset(dis,0x3f,sizeof(dis));
dis[(x[1]-1)*m+y[1]]=0;
pq.push({0,(x[1]-1)*m+y[1]});
while(!pq.empty()){
int tp=pq.top().second;
pq.pop();
if(vs[tp]) continue;
vs[tp]=1;
for(int i=0;i<v[tp].size();i++){
if(vs[v[tp][i].x]) continue;
if(dis[v[tp][i].x]>dis[tp]+v[tp][i].y){
dis[v[tp][i].x]=dis[tp]+v[tp][i].y;
pq.push({-dis[v[tp][i].x],v[tp][i].x});
}
}
}
cout<<dis[(x[s]-1)*m+y[s]];
return 0;
}