#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll,int> ii;
#define fi first
#define se second
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
ll A,B,C;
int n,h,w;
ll dp0[505][505], dp1[505][505][4];
bool player[505][505];
int min_distance[505][505];
void prep(){
queue <int> q;
for(int i=0;i<=h;i++)
for(int j=0;j<=w;j++){
if (player[i][j]) min_distance[i][j] = 0, q.push(i * 501 + j);
else min_distance[i][j] = 100000;
}
while(q.size()){
int x = q.front() / 501;
int y = q.front() % 501;
q.pop();
for(int k=0;k<4;k++){
int X = x + dx[k];
int Y = y + dy[k];
if (0 > X || X > h || 0 > Y || Y > w) continue;
if (min_distance[X][Y] > min_distance[x][y] + 1)
min_distance[X][Y] = min_distance[x][y] + 1,
q.push(X * 501 + Y);
}
}
}
#define x1 asd
#define y1 jnda
#define xn addaf
#define yn nln
int x1,y1,xn,yn;
void prep_dp(){
for(int i=0;i<=h;i++)
for(int j=0;j<=w;j++)
dp0[i][j] = dp1[i][j][0] = dp1[i][j][1] = dp1[i][j][2] = dp1[i][j][3] = (ll) 1e18;
dp0[x1][y1] = 0;
}
void cal_dp(){
for(int _time=0;_time<=1;_time++){
priority_queue <ii,vector<ii>,greater<ii> > pq;
for(int i=0;i<=h;i++)
for(int j=0;j<=w;j++)
pq.push(ii(dp0[i][j], i*3500 + j * 5 + 0));
while(pq.size()){
int x = pq.top().se / 3500;
int y = (pq.top().se % 3500) / 5;
int type = pq.top().se % 5;
ll dis = pq.top().fi;
pq.pop();
if (type == 0 && dp0[x][y] != dis) continue;
if (type && dp1[x][y][type-1] != dis) continue;
if (type == 0){
for(int k=0;k<4;k++){
int X = x + dx[k];
int Y = y + dy[k];
if (0 > X || X > h || 0 > Y || Y > w) continue;
if (dp1[X][Y][k] > dp0[x][y] + A + B)
dp1[X][Y][k] = dp0[x][y] + A + B,
pq.push(ii(dp1[X][Y][k], X * 3500 + Y * 5 + k+1));
if (dp0[X][Y] > dp0[x][y] + C)
dp0[X][Y] = dp0[x][y] + C,
pq.push(ii(dp0[X][Y], X * 3500 + Y * 5 + 0));
}
}
else{
int X = x + dx[type-1];
int Y = y + dy[type-1];
if (0 > X || X > h || 0 > Y || Y > w) continue;
if (dp1[X][Y][type-1] > dp1[x][y][type-1] + A)
dp1[X][Y][type-1] = dp1[x][y][type-1] + A,
pq.push(ii(dp1[X][Y][type-1], X * 3500 + Y * 5 + type));
}
}
/*
for(int i=0;i<=h;i++)
for(int j=0;j<=w;j++)
for(int t=0;t<4;t++)
dp0[i][j] = min(dp0[i][j], dp1[i][j][t] + min_distance[i][j] * C),
dp1[i][j][t] = (ll) 1e18;
for(int i=0;i<=h;i++){
for(int j=0;j<=w;j++){
if (dp0[i][j] != (ll) 1e18) cout << dp0[i][j] << ' ';
else cout << -1;
}
cout << endl;
}
cout << endl;
*/
}
}
int main(){
iostream::sync_with_stdio(0);
cin >> h >> w;
cin >> A >> B >> C;
cin >> n;
for(int i=1;i<=n;i++){
int x,y;
cin >> x >> y;
if (i == 1) x1 = x, y1 = y;
if (i == n) xn = x, yn = y;
player[x][y] = 1;
}
prep();
prep_dp();
cal_dp();
cout << dp0[xn][yn];
}
/*
500 500
1 3 6
3
1 1
0 4
6 5
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
83 ms |
15468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
356 ms |
21612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
83 ms |
15468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
