#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<pll , ll> plll;
typedef pair<ll , plll> pllll;
const ll maxn = 502 , inf = 2e18;
ll n , m , A , B , C;
ll dis[maxn][maxn][5];
short int f[maxn][maxn];
vector<pll> bfs;
priority_queue<pllll , vector<pllll> , greater<pllll>> pq;
void BFS(){
ll x = 0;
while(x < sze(bfs)){
ll i = bfs[x].first , j = bfs[x++].second;
if(i > 0){
if(f[i - 1][j] > f[i][j]){
f[i - 1][j] = f[i][j] + 1;
bfs.push_back({i - 1 , j});
}
}
if(j > 0){
if(f[i][j - 1] > f[i][j]){
f[i][j - 1] = f[i][j] + 1;
bfs.push_back({i , j - 1});
}
}
if(i < n){
if(f[i + 1][j] > f[i][j]){
f[i + 1][j] = f[i][j] + 1;
bfs.push_back({i + 1 , j});
}
}
if(j < m){
if(f[i][j + 1] > f[i][j]){
f[i][j + 1] = f[i][j] + 1;
bfs.push_back({i , j + 1});
}
}
}
return;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
memset(f , 63 , sizeof(f));
memset(dis , 63 , sizeof(dis));
ll k , x , y;
cin>>n>>m>>A>>B>>C>>k;
for(ll i = 0 ; i < k ; i++){
cin>>x>>y;
if(i == 0){
dis[x][y][0] = 0;
pq.push({0 , {{x , y} , 0}});
}
if(f[x][y] > 0) bfs.push_back({x , y});
f[x][y] = 0;
}
BFS();
// while(!pq.empty()){
// pllll p = pq.top(); pq.pop();
// ll i = p.second.first.first , j = p.second.first.second , t = p.second.second;
// if(dis[i][j][t] != p.first) continue;
// if(t == 0){
// ll ps = dis[i][j][0] + B;
// if(dis[i][j][1] > ps){
// dis[i][j][1] = ps;
// pq.push({ps , {{i , j} , 1}});
// }
// if(dis[i][j][2] > ps){
// dis[i][j][2] = ps;
// pq.push({ps , {{i , j} , 2}});
// }
// if(dis[i][j][3] > ps){
// dis[i][j][3] = ps;
// pq.push({ps , {{i , j} , 3}});
// }
// if(dis[i][j][4] > ps){
// dis[i][j][4] = ps;
// pq.push({ps , {{i , j} , 4}});
// }
// ll dr = dis[i][j][0] + C;
// if(i > 0){
// if(dis[i - 1][j][0] > dr){
// dis[i - 1][j][0] = dr;
// pq.push({dr , {{i - 1 , j} , 0}});
// }
// }
// if(j > 0){
// if(dis[i][j - 1][0] > dr){
// dis[i][j - 1][0] = dr;
// pq.push({dr , {{i , j - 1} , 0}});
// }
// }
// if(i < n){
// if(dis[i + 1][j][0] > dr){
// dis[i + 1][j][0] = dr;
// pq.push({dr , {{i + 1 , j} , 0}});
// }
// }
// if(j < m){
// if(dis[i][j + 1][0] > dr){
// dis[i][j + 1][0] = dr;
// pq.push({dr , {{i , j + 1} , 0}});
// }
// }
// } else {
// ll rc = dis[i][j][t] + f[i][j] * C;
// if(dis[i][j][0] > rc){
// dis[i][j][0] = rc;
// pq.push({rc , {{i , j} , 0}});
// }
// }
// if(t == 1){
// ll ps = dis[i][j][1] + A;
// if(i > 0){
// if(dis[i - 1][j][1] > ps){
// dis[i - 1][j][1] = ps;
// pq.push({ps , {{i - 1 , j} , 1}});
// }
// }
// } else if(t == 2){
// ll ps = dis[i][j][2] + A;
// if(i < n){
// if(dis[i + 1][j][2] > ps){
// dis[i + 1][j][2] = ps;
// pq.push({ps , {{i + 1 , j} , 2}});
// }
// }
// } else if(t == 3){
// ll ps = dis[i][j][3] + A;
// if(j > 0){
// if(dis[i][j - 1][3] > ps){
// dis[i][j - 1][3] = ps;
// pq.push({ps , {{i , j - 1} , 3}});
// }
// }
// } else if(t == 4){
// ll ps = dis[i][j][4] + A;
// if(j < m){
// if(dis[i][j + 1][4] > ps){
// dis[i][j + 1][4] = ps;
// pq.push({ps , {{i , j + 1} , 4}});
// }
// }
// }
// }
// ll ans = inf;
// for(ll j = 0 ; j < 5 ; j++) ans = min(ans , dis[x][y][j]);
// cout<<ans<<'\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
231 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
249 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
231 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
