#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e2 + 2, MOD = (int)1e9 + 7;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int n,m,d[N][N];
ll val[N][N];
ll a,b,c;
queue<pair<int,int>> q;
bool check(int x,int y){
return (x >= 1 && x <= n && y >= 1 && y <= m);
}
int fx,fy;
ll dist[4][2][N][N];
const ll inf = 1e17;
set<array<ll,5>> st;
void test(){
cin >> n >> m >> a >> b >> c;
n++;
m++;
int f;cin >> f;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
d[i][j] = 1e9;
for(int dir = 0;dir < 4;dir++)
{
dist[dir][0][i][j] = inf;
dist[dir][1][i][j] = inf;
}
}
}
for(int i = 1;i <= f;i++) {
int s,t;
cin >> s >> t;
s++;
t++;
if(i == 1){
for(int dir = 0;dir < 4;dir++){
dist[1][dir][s][t] = 0;
st.insert({0,dir,1,s,t});
}
}
d[s][t] = 0;
q.push({s,t});
fx = s;fy = t;
}
while(!q.empty()){
auto [x,y] = q.front();q.pop();
val[x][y] = d[x][y] * c;
for(int i = 0;i < 4;i++){
int x1 = x + dx[i],y1 = y + dy[i];
if(check(x1,y1) && d[x1][y1] > d[x][y] + 1){
d[x1][y1] = d[x][y] +1;
q.push({x1,y1});
}
}
}
while(!st.empty())
{
auto [D,di,is,x,y] = (*st.begin());
//cout << is << ' ' << x << ' ' << y << ' ' << D << '\n';
st.erase(st.begin());
if(is){
for(int dir = 0;dir < 4;dir++){
ll du = D + c;
int i = x + dx[dir],j = y + dy[dir];
if(check(i,j) && dist[dir][1][i][j] > du){
st.erase({dist[dir][1][i][j],dir,1,i,j});
dist[dir][1][i][j] = du;
st.insert({du,dir,1,i,j});
}
du = D + a + b;
i = x + dx[dir],j = y + dy[dir];
if(check(i,j) && dist[dir][0][i][j] > du){
st.erase({dist[dir][0][i][j],dir,0,i,j});
dist[dir][0][i][j] = du;
st.insert({du,dir,0,i,j});
}
}
}
else{
int i = x + dx[di],j = y + dy[di];
ll du = D + a;
if(check(i,j) && du < dist[di][0][i][j])
{
st.erase({dist[di][0][i][j],di,0,i,j});
dist[di][0][i][j] = du;
st.insert({dist[di][0][i][j],di,0,i,j});
}
du = D + val[x][y];
if(du < dist[di][1][x][y]){
st.erase({dist[di][1][x][y],di,1,x,y});
dist[di][1][x][y] = du;
st.insert({du,di,1,x,y});
}
}
}
ll res = inf;
for(int i = 0;i < 4;i++)
{
res = min(res,dist[i][0][fx][fy]);
res = min(res,dist[i][1][fx][fy]);
}
cout << res << '\n';
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--){
test();
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
14 ms |
38232 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
15 ms |
38488 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
14 ms |
38232 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
