| 比赛 |
果蝇王邀请赛div2 |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
雪王与果蝇王游于濠梁之上 |
最终得分 |
100 |
| 用户昵称 |
李金泽 |
运行时间 |
3.761 s |
| 代码语言 |
C++ |
内存使用 |
18.32 MiB |
| 提交时间 |
2026-08-27 12:33:44 |
显示代码纯文本
#include<bits/stdc++.h>
#define N 100005
#define M 505
#define int long long
#define db double
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int T,n,m,k,A,B,C,sx,sy,tx,ty,d[M][M][5],p[M][M],op,x,y,z,ans,last;
int nx[4]={-1,0,1,0},ny[4]={0,-1,0,1};
const int inf=0x3f3f3f3f3f3f3f3f;
bool vis[M][M];
struct nd{int x,y,k,w;bool operator<(nd y)const{return w>y.w;}};
struct node{int x,y;};
void swap(int &x,int &y){int t=x;x=y;y=t;}
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
void ckmax(int &x,int y){if(y>x)x=y;}
void ckmin(int &x,int y){if(y<x)x=y;}
int fp(int a,int n,int mod){
int ans=1;
while(n){
if(n&1)ans=ans*a%mod;
a=a*a%mod;
n>>=1;
}
return ans;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int po(int x){return x*x;}
int sub(int x,int y){return x>y?x-y:y-x;}
int ab(int x){return x<0?-x:x;}
int read(){
int sum=0;bool f=0;char c=getchar();
for(;c<48||c>57;c=getchar())if(c==45)f=1;
for(;c>=48&&c<=57;c=getchar())sum=sum*10+(c&15);
return f?-sum:sum;
}
int dis(int x1,int y1,int x2,int y2){
return sub(x1,x2)+sub(y1,y2);
}
void init(){
memset(p,0x3f,sizeof(p));
queue<node>q;
fo(i,0,n)fo(j,0,m)if(vis[i][j])p[i][j]=0,q.push({i,j});
while(!q.empty()){
node u=q.front();q.pop();
fo(k,0,3){
int tx=u.x+nx[k],ty=u.y+ny[k];
if(tx<0||ty<0||tx>n||ty>m||p[tx][ty]!=inf)continue;
p[tx][ty]=p[u.x][u.y]+1;
q.push({tx,ty});
}
}
}
int dijkstra(){
memset(d,0x3f,sizeof(d));
priority_queue<nd>q;
d[sx][sy][4]=0;q.push({sx,sy,4});
while(!q.empty()){
nd u=q.top();q.pop();
if(u.w>d[u.x][u.y][u.k])continue;
if(u.x==tx&&u.y==ty)return u.w;
if(u.k<4&&u.w+p[u.x][u.y]*C<d[u.x][u.y][4]){
d[u.x][u.y][4]=u.w+p[u.x][u.y]*C;
q.push({u.x,u.y,4,u.w+p[u.x][u.y]*C});
}
if(u.k==4)
fo(k,0,3){
int tx=u.x+nx[k],ty=u.y+ny[k];
if(tx<0||ty<0||tx>n||ty>m)continue;
if(u.w+A+B<d[tx][ty][k]){
d[tx][ty][k]=u.w+A+B;
q.push({tx,ty,k,u.w+A+B});
}
if(u.w+C<d[tx][ty][4]){
d[tx][ty][4]=u.w+C;
q.push({tx,ty,4,u.w+C});
}
}
else{
int tx=u.x+nx[u.k],ty=u.y+ny[u.k];
if(tx<0||ty<0||tx>n||ty>m||u.w+A>=d[tx][ty][u.k])continue;
d[tx][ty][u.k]=u.w+A;
q.push({tx,ty,u.k,u.w+A});
}
}
return -1;
}
signed main(){
freopen("play.in","r",stdin);freopen("play.out","w",stdout);
n=read();m=read();
A=read();B=read();C=read();
z=read();
fo(i,1,z){
x=read(),y=read();
vis[x][y]=1;
if(i==1)sx=x,sy=y;
if(i==z)tx=x,ty=y;
}
if(A>=C)return !printf("%lld",dis(sx,sy,tx,ty)*C);
init();
printf("%lld",dijkstra());
return 0;
}