#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int type;
int val;
int x, y;
bool operator<(const node & a)const{
return val < a.val;
}
};
signed main(){
int X, Y, A, B, C, N;
cin >> X >> Y >> A >> B >> C >> N;
vector<pair<int,int>> players(N);
vector<vector<int>> pos(X + 10, vector<int>(Y + 10, 1e9));
queue<array<int, 3>> populate;
for(int i = 0; i < N; i ++){
cin >> players[i].first >> players[i].second;
populate.push({players[i].first, players[i].second, 0});
}
while(!populate.empty()){
int x = populate.front()[0], y = populate.front()[1], c = populate.front()[2];
populate.pop();
if(pos[x][y] <= c)continue;
if(x > 0)populate.push({x - 1, y , c+ 1});
if(y > 0)populate.push({x, y-1, c+1});
if(x < X)populate.push({x + 1, y, c + 1});
if(y < Y)populate.push({x, y + 1, c + 1});
pos[x][y] = c;
}
vector<vector<vector<int>>> arr(X + 5, vector<vector<int>>(Y + 5, vector<int>(3, 1e17)));
arr[players[0].first][players[0].second][2] = 0;
priority_queue<node> que;
que.push({2, 0, players[0].first,players[0].second});
while(!que.empty()){
node a = que.top();
que.pop();
if(arr[a.x][a.y][a.type] != a.val)continue;
if(a.type == 2){
if(a.x > 0 && arr[a.x-1][a.y][2] > a.val + C){que.push({2, a.val+C, a.x-1, a.y});arr[a.x-1][a.y][2] = a.val+C;}
if(a.y > 0 && arr[a.x][a.y-1][2] > a.val + C){que.push({2, a.val+C, a.x, a.y-1});arr[a.x][a.y-1][2] = a.val+C;}
if(a.x < X && arr[a.x+1][a.y][2] > a.val + C){que.push({2, a.val+C, a.x+1, a.y});arr[a.x+1][a.y][2] = a.val+C;}
if(a.y < Y && arr[a.x][a.y+1][2] > a.val + C){que.push({2, a.val+C, a.x, a.y+1});arr[a.x][a.y+1][2] = a.val+C;}
if(a.val + B < arr[a.x][a.y][0]){que.push({0, a.val+B, a.x, a.y});arr[a.x][a.y][0] = a.val+B;}
if(a.val + B < arr[a.x][a.y][1]){que.push({1, a.val+B, a.x, a.y});arr[a.x][a.y][1] = a.val+B;}
}
if(a.type == 1){
if(a.y > 0 && arr[a.x][a.y - 1][1] > a.val + A){que.push({1, a.val+A, a.x, a.y - 1});arr[a.x][a.y - 1][1] = a.val+A;}
if(a.y < Y && arr[a.x][a.y + 1][1] > a.val + A){que.push({1, a.val+A, a.x, a.y + 1});arr[a.x][a.y + 1][1] = a.val+A;}
if(a.val + pos[a.x][a.y] * C < arr[a.x][a.y][2]){que.push({2, a.val + pos[a.x][a.y] * C, a.x, a.y}); arr[a.x][a.y][2] = a.val + pos[a.x][a.y] * C;}
}
if(a.type == 0){
if(a.x > 0 && arr[a.x - 1][a.y][0] > a.val + A){que.push({0, a.val+A, a.x - 1, a.y});arr[a.x - 1][a.y][0] = a.val+A;}
if(a.x < X && arr[a.x + 1][a.y][0] > a.val + A){que.push({0, a.val+A, a.x + 1, a.y});arr[a.x + 1][a.y][0] = a.val+A;}
if(a.val + pos[a.x][a.y] * C < arr[a.x][a.y][2]){que.push({2, a.val + pos[a.x][a.y] * C, a.x, a.y}); arr[a.x][a.y][2] = a.val + pos[a.x][a.y] * C;}
}
}
cout << arr[players.back().first][players.back().second][2] << endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3024 ms |
6352 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3036 ms |
24612 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3024 ms |
6352 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
