#include <bits/stdc++.h>
using namespace std;
int odl[507][507];
int odl2[507][507][5];
int dx[4];
int dy[4];
int h, w;
bool czyok(int i, int j)
{
if(0 <= i && i <= h && 0 <= j && j <= w)
{
return true;
}
return false;
}
int main()
{
dx[0] = 1;
dx[1] = -1;
dy[2] = 1;
dy[3] = -1;
int a, b, c, n;
cin >> h >> w >> a >> b >> c >> n;
for(int i = 0; i <= h; i++)
{
for(int j = 0; j <= w; j++)
{
for(int k = 0; k < 5; k++)
{
odl2[i][j][k] = INT_MAX;
}
odl[i][j] = INT_MAX;
}
}
vector<pair<int, int>> osoby;
queue<pair<int, int>> q;
for(int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
osoby.push_back({x, y});
q.push({x, y});
odl[x][y] = 0;
}
while(!q.empty())
{
auto cur = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int curx = cur.first + dx[i];
int cury = cur.second + dy[i];
if(czyok(curx, cury) && odl[curx][cury] > odl[cur.first][cur.second] + 1)
{
odl[curx][cury] = odl[cur.first][cur.second] + 1;
q.push({curx, cury});
}
}
}
priority_queue<pair<pair<int, int>, pair<int, int>>, vector<pair<pair<int, int>, pair<int, int>>>, greater<pair<pair<int, int>, pair<int, int>>>> pq;
pq.push({{0, 0}, {osoby[0].first, osoby[0].second}});
odl2[osoby[0].first][osoby[0].second][0] = 0;
while(!pq.empty())
{
auto cur = pq.top();
pq.pop();
if(odl2[cur.second.first][cur.second.second][cur.first.second] < cur.first.first)
{
continue;
}
if(cur.first.second == 0)
{
for(int i = 0; i < 4; i++)
{
int i2, j;
int curodl = odl2[cur.second.first][cur.second.second][cur.first.second];
i2 = cur.second.first;
j = cur.second.second;
/*if(i2 == 3 && j == 1)
{
cout << odl2[i2][j][i + 1] << endl;
}*/
if(odl2[i2][j][i + 1] > curodl + b)
{
odl2[i2][j][i + 1] = curodl + b;
pq.push({{odl2[i2][j][i + 1], i + 1}, {i2, j}});
}
if(czyok(i2 + dx[i], j + dy[i]) && odl2[i2 + dx[i]][j + dy[i]][0] > curodl + c)
{
odl2[i2 + dx[i]][j + dy[i]][0] = curodl + c;
pq.push({{odl2[i2 + dx[i]][j + dy[i]][0], 0}, {i2 + dx[i], j + dy[i]}});
}
}
}
else
{
int curodl = odl2[cur.second.first][cur.second.second][cur.first.second];
int i, j, typ;
i = cur.second.first;
j = cur.second.second;
typ = cur.first.second;
if(i == 3 && j == 1 && typ == 4)
{
//cout << "tak" << endl;
//cout << odl[i][j] << endl;
}
if(curodl + odl[i][j] * c < odl2[i][j][0])
{
odl2[i][j][0] = curodl + odl[i][j] * c;
pq.push({{odl2[i][j][0], 0}, {i, j}});
}
if(czyok(i + dx[typ - 1], j + dy[typ - 1]) && odl2[i + dx[typ - 1]][j + dy[typ - 1]][typ] > curodl + a)
{
odl2[i + dx[typ - 1]][j + dy[typ - 1]][typ] = curodl + a;
pq.push({{odl2[i + dx[typ - 1]][j + dy[typ - 1]][typ], typ}, {i + dx[typ - 1], j + dy[typ - 1]}});
}
}
}
/*for(int i = 0; i <= h; i++)
{
for(int j = 0; j <= w; j++)
{
cout << odl2[i][j][0] << " ";
}
cout << endl;
}*/
cout << odl2[osoby[n - 1].first][osoby[n - 1].second][0] << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |