#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define mid ((l+r)>>1)
#define endl "\n"
#define pq_min(a) priority_queue<a,vector<a>,greater<a>>
#define lll array<ll,3>
#define pb push_back
#define ppb pop_back
using namespace std;
using vi = vector<int>;
const ll inf=1e18;
const int mov[4][2]{
{1,0},
{0,1},
{-1,0},
{0,-1}
};
inline ll abss(ll a){
if(a>=0) return a;
return -a;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll h, w, a, b, c, n;
cin>>h>>w>>a>>b>>c>>n;
h++;
w++;
int s[n], t[n];
ll dis[h+2][w+2], vis[h+2][w+2]{}, cr[h+1][w+1], cc[h+1][w+1];
rep(i,0,n){
cin>>s[i]>>t[i];
s[i]++;
t[i]++;
vis[s[i]][t[i]]=true;
}
rep(i,1,h+1) rep(j,1,w+1) cc[i][j]=cr[i][j]=inf;
rep(i,1,h+1){
ll mn=inf;
rep(j,1,w+1){
if(vis[i][j]) mn=0;
cc[i][j]=min(cc[i][j],mn);
mn++;
}
mn=inf;
repr(j,w+1,1){
if(vis[i][j]) mn=0;
cc[i][j]=min(cc[i][j],mn);
mn++;
}
}
rep(j,1,w+1){
ll mn=inf;
rep(i,1,h+1){
if(vis[i][j]) mn=0;
cr[i][j]=min(cr[i][j],mn);
mn++;
}
mn=inf;
repr(i,h+1,1){
if(vis[i][j]) mn=0;
cr[i][j]=min(cr[i][j],mn);
mn++;
}
}
rep(i,0,h+2) rep(j,0,w+2) vis[i][j]=1;
rep(i,1,h+1) rep(j,1,w+1) vis[i][j]=0;
rep(i,0,h+2) rep(j,0,w+2) dis[i][j]=inf;
pq_min(lll) pq;
pq.push({0,s[0],t[0]});
dis[s[0]][t[0]]=0;
while(pq.size()){
ll x=pq.top()[1], y=pq.top()[2], W=pq.top()[0], z;
pq.pop();
if(vis[x][y]) continue;
vis[x][y]=true;
rep(i,0,4){
x+=mov[i][0];
y+=mov[i][1];
if(!vis[x][y] && dis[x][y]>W+c){
dis[x][y]=W+c;
pq.push({dis[x][y],x,y});
}
x-=mov[i][0];
y-=mov[i][1];
}
if(a<c){
rep(i,1,h+1){
if(cc[i][y]<inf) z=min(inf,W+a*abss(x-i)+b+c*cc[i][y]);
else z=inf;
if(!vis[i][y] && dis[i][y]>z){
dis[i][y]=z;
pq.push({z,i,y});
}
}
rep(i,1,w+1){
if(cr[x][i]<inf) z=min(inf,W+a*abss(y-i)+b+c*cr[x][i]);
else z=inf;
if(!vis[x][i] && dis[x][i]>z){
dis[x][i]=z;
pq.push({z,x,i});
}
}
}
}
cout<<dis[s[n-1]][t[n-1]]<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |