#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 501;
const ll K = 1e5;
const ll inf = 1e18;
struct point{
ll x,y;
};
ll dist[N][N][3];
ll dist2[N][N];
bool vis[N][N];
point player[K];
priority_queue <array<ll,4>> pq;
queue <array<ll,2>> q;
ll d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
ll n,m,a,b,c;
ll k;
bool inbound(ll x,ll y){
return 0 <= x && x <= n && 0 <= y && y <= m;
}
void add(ll nr,ll x,ll y,ll id){
if(dist[x][y][id] > nr){
dist[x][y][id] = nr;
pq.push({-nr,x,y,id});
}
}
void bfs(){
for(ll i = 0;i < k;i++){
q.push({player[i].x,player[i].y});
vis[player[i].x][player[i].y] = 1;
dist2[player[i].x][player[i].y] = 0;
}
while(!q.empty()){
ll x = q.front()[0];
ll y = q.front()[1];
q.pop();
for(ll l = 0;l < 4;l++){
ll nx = x + d[l][0];
ll ny = y + d[l][1];
if(inbound(nx,ny) && !vis[nx][ny]){
vis[nx][ny] = 1;
dist2[nx][ny] = dist2[x][y] + 1;
q.push({nx,ny});
}
}
}
}
int main(){
cin>>n>>m;
cin>>a>>b>>c;
cin>>k;
for(ll i = 0;i < k;i++){
cin>>player[i].x>>player[i].y;
}
for(ll i = 0;i <= n;i++){
for(ll j = 0;j <= m;j++){
for(ll l = 0;l < 3;l++){
dist[i][j][l] = inf;
}
}
}
bfs();
pq.push({0,player[0].x,player[0].y,0});
dist[player[0].x][player[0].y][0] = 0;
///0 - on player
///1 - thrown left/right
///2 - thrown up/down
while(!pq.empty()){
auto x = pq.top();
x[0] = -x[0];
pq.pop();
if(x[0] != dist[x[1]][x[2]][x[3]]){
continue;
}
if(x[3] == 0){
///throw ball
add(x[0] + b,x[1],x[2],1);
add(x[0] + b,x[1],x[2],2);
///directional movement
for(ll l = 0;l < 4;l++){
ll nx = x[1] + d[l][0];
ll ny = x[2] + d[l][1];
if(inbound(nx,ny)){
add(x[0] + c,nx,ny,x[3]);
}
}
}else if(x[3] == 1){
///catch
add(x[0] + dist2[x[1]][x[2]]*c,x[1],x[2],0);
///directional movement
for(ll l = 2;l < 4;l++){
ll nx = x[1] + d[l][0];
ll ny = x[2] + d[l][1];
if(inbound(nx,ny)){
add(x[0] + a,nx,ny,x[3]);
}
}
}else{
///catch
add(x[0] + dist2[x[1]][x[2]]*c,x[1],x[2],0);
///directional movement
for(ll l = 0;l < 2;l++){
ll nx = x[1] + d[l][0];
ll ny = x[2] + d[l][1];
if(inbound(nx,ny)){
add(x[0] + a,nx,ny,x[3]);
}
}
}
}
/*for(ll i = 0;i <= n;i++){
for(ll j = 0;j <= m;j++){
cout<<dist[i][j][0]<<' ';
}
cout<<'\n';
}*/
cout<<dist[player[k - 1].x][player[k - 1].y][0]<<'\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
7820 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
173 ms |
20232 KB |
Output is correct |
4 |
Correct |
166 ms |
16832 KB |
Output is correct |
5 |
Correct |
35 ms |
5612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
168 ms |
16748 KB |
Output is correct |
2 |
Correct |
183 ms |
16828 KB |
Output is correct |
3 |
Correct |
122 ms |
18864 KB |
Output is correct |
4 |
Correct |
118 ms |
18108 KB |
Output is correct |
5 |
Correct |
129 ms |
19644 KB |
Output is correct |
6 |
Correct |
113 ms |
19388 KB |
Output is correct |
7 |
Correct |
168 ms |
18436 KB |
Output is correct |
8 |
Correct |
133 ms |
18952 KB |
Output is correct |
9 |
Correct |
154 ms |
19904 KB |
Output is correct |
10 |
Correct |
25 ms |
11428 KB |
Output is correct |
11 |
Correct |
150 ms |
19460 KB |
Output is correct |
12 |
Correct |
166 ms |
18912 KB |
Output is correct |
13 |
Correct |
74 ms |
18116 KB |
Output is correct |
14 |
Correct |
145 ms |
18792 KB |
Output is correct |
15 |
Correct |
108 ms |
19388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
7820 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
173 ms |
20232 KB |
Output is correct |
4 |
Correct |
166 ms |
16832 KB |
Output is correct |
5 |
Correct |
35 ms |
5612 KB |
Output is correct |
6 |
Correct |
168 ms |
16748 KB |
Output is correct |
7 |
Correct |
183 ms |
16828 KB |
Output is correct |
8 |
Correct |
122 ms |
18864 KB |
Output is correct |
9 |
Correct |
118 ms |
18108 KB |
Output is correct |
10 |
Correct |
129 ms |
19644 KB |
Output is correct |
11 |
Correct |
113 ms |
19388 KB |
Output is correct |
12 |
Correct |
168 ms |
18436 KB |
Output is correct |
13 |
Correct |
133 ms |
18952 KB |
Output is correct |
14 |
Correct |
154 ms |
19904 KB |
Output is correct |
15 |
Correct |
25 ms |
11428 KB |
Output is correct |
16 |
Correct |
150 ms |
19460 KB |
Output is correct |
17 |
Correct |
166 ms |
18912 KB |
Output is correct |
18 |
Correct |
74 ms |
18116 KB |
Output is correct |
19 |
Correct |
145 ms |
18792 KB |
Output is correct |
20 |
Correct |
108 ms |
19388 KB |
Output is correct |
21 |
Correct |
33 ms |
9052 KB |
Output is correct |
22 |
Correct |
169 ms |
18868 KB |
Output is correct |
23 |
Correct |
161 ms |
14864 KB |
Output is correct |
24 |
Correct |
176 ms |
16060 KB |
Output is correct |
25 |
Correct |
158 ms |
18364 KB |
Output is correct |
26 |
Correct |
181 ms |
20200 KB |
Output is correct |
27 |
Correct |
148 ms |
12632 KB |
Output is correct |
28 |
Correct |
133 ms |
13148 KB |
Output is correct |
29 |
Correct |
184 ms |
18164 KB |
Output is correct |
30 |
Correct |
116 ms |
12372 KB |
Output is correct |
31 |
Correct |
143 ms |
20492 KB |
Output is correct |
32 |
Correct |
207 ms |
22356 KB |
Output is correct |
33 |
Correct |
130 ms |
19656 KB |
Output is correct |
34 |
Correct |
201 ms |
19768 KB |
Output is correct |
35 |
Correct |
109 ms |
12368 KB |
Output is correct |