#include<bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define int long long
using namespace std;
const int INF=1e18,MX=600;
int h,w,a,b,c,n,pref[505][505],dp[505][505],g1[505],g2[505],s[100005][2];
signed main(void){
exoworldgd;
cin>>h>>w>>a>>b>>c>>n,h++,w++;
for(int i=0;i<h;i++)for(int j=0;j<w;j++)pref[i][j]=INF;
for(int i=0;i<n;i++)cin>>s[i][0]>>s[i][1],pref[s[i][0]][s[i][1]]=0;
if(c<=a){cout<<(abs(s[0][0]-s[n-1][0])+abs(s[0][1]-s[n-1][1]))*c;return 0;}
set<array<int,2>>st;
for(int i=0;i<n;i++)st.insert({0,s[i][0]*w+s[i][1]});
for(int i,j;st.size();){
i=st.begin()->at(1)/w,j=st.begin()->at(1)%w,st.erase(st.begin());
for(int ij=max(0LL,j-1);ij<min(j+2,w);ij++)if(pref[i][ij]>pref[i][j]+abs(ij-j)*c)st.erase({pref[i][ij],i*w+ij}),pref[i][ij]=pref[i][j]+abs(ij-j)*c,st.insert({pref[i][ij],i*w+ij});
for(int ij=max(0LL,i-1);ij<min(i+2,h);ij++)if(pref[ij][j]>pref[i][j]+abs(ij-i)*c)st.erase({pref[ij][j],ij*w+j}),pref[ij][j]=pref[i][j]+abs(i-ij)*c,st.insert({pref[ij][j],ij*w+j});
}
for(int i=0;i<h;i++)for(int j=0;j<w;j++)dp[i][j]=INF;
dp[s[0][0]][s[0][1]]=0,st.insert({0,s[0][0]*w+s[0][1]});
while(st.size()){
int i=st.begin()->at(1)/w,j=st.begin()->at(1)%w;
if(dp[s[n-1][0]][s[n-1][1]]<=c+st.begin()->at(0)&&dp[s[n-1][0]][s[n-1][1]]<=a+b+st.begin()->at(0)){cout<<dp[s[n-1][0]][s[n-1][1]];return 0;}
st.erase(st.begin());
if(g1[i]<MX){
g1[i]++;
for(int ij=0;ij<w;ij++)if(dp[i][ij]>dp[i][j]+abs(ij-j)*a+b+pref[i][ij])st.erase({dp[i][ij],i*w+ij}),dp[i][ij]=dp[i][j]+abs(ij-j)*a+b+pref[i][ij],st.insert({dp[i][ij],i*w+ij});
}
if(g2[j]<MX){
g2[j]++;
for(int ij=0;ij<h;ij++)if(dp[ij][j]>dp[i][j]+abs(ij-i)*a+b+pref[ij][j])st.erase({dp[ij][j],ij*w+j}),dp[ij][j]=dp[i][j]+abs(i-ij)*a+b+pref[ij][j],st.insert({dp[ij][j],ij*w+j});
}
for(int ij=max(0LL,j-1);ij<min(j+2,w);ij++)if(dp[i][ij]>dp[i][j]+abs(ij-j)*c)st.erase({dp[i][ij],i*w+ij}),dp[i][ij]=dp[i][j]+abs(ij-j)*c,st.insert({dp[i][ij],i*w+ij});
for(int ij=max(0LL,i-1);ij<min(i+2,h);ij++)if(dp[ij][j]>dp[i][j]+abs(ij-i)*c)st.erase({dp[ij][j],ij*w+j}),dp[ij][j]=dp[i][j]+abs(i-ij)*c,st.insert({dp[ij][j],ij*w+j});
}
cout<<dp[s[n-1][0]][s[n-1][1]];
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |