#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define wczytaj(a, c, n) a.resize(n); f(i, c, n) cin >> a[i];
#define sz(a) int(a.size())
#define wypisz(a, c) f(i, c, sz(a)) cout << a[i] << " "; cout << "\n";
int h, w; //wysokosc (height) - h metrow, szeorkosc (weidht) w metrow
int n;
ll a, b, c; //koszt to odl * a + b, ruch to c
vector<pair<int, int>> zawodnicy; //{y zawodnika , x zawodnika}
vector<vector<ll>> min_dojscie;
queue<pair<pair<int, int>, ll>> kolejka_bfs;
vector<pair<int, int>> ruchy = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
pair<int, int> p1, p2;
pair<pair<int, int>, ll> p3;
pair<pair<ll, int>, pair<int, int>> p4; //koszt , wymiar, y, x
vector<vector<vector<ll>>> dijkstra;
bool dobre(pair<int, int> pos) {
if (pos.st < 0 || pos.st > h || pos.nd < 0 || pos.nd > w) return false;
return true;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> h >> w >> a >> b >> c >> n;
zawodnicy.resize(n + 1);
f(i, 1, n + 1) cin >> zawodnicy[i].st >> zawodnicy[i].nd;
min_dojscie.resize(h + 1, vector<ll>(w + 1, -1));
f(i, 1, n) {
min_dojscie[zawodnicy[i].st][zawodnicy[i].nd] = 0;
kolejka_bfs.push({{zawodnicy[i].st, zawodnicy[i].nd}, 0});
}
while (kolejka_bfs.size()) {
p3 = kolejka_bfs.front();
p1 = p3.st;
kolejka_bfs.pop();
for (pair<int, int> ele: ruchy) {
p2 = {p1.st + ele.st, p1.nd + ele.nd};
if (!dobre(p2)) continue;
if (min_dojscie[p2.st][p2.nd] != -1) continue;
min_dojscie[p2.st][p2.nd] = p3.nd + c;
kolejka_bfs.push({{p2.st, p2.nd}, min_dojscie[p2.st][p2.nd]});
}
}
dijkstra.resize(5, vector<vector<ll>>(h + 1, vector<ll>(w + 1, -1)));
priority_queue<pair<pair<ll, int>, pair<int, int>>> kolejka_dijsktra;
kolejka_dijsktra.push({{0, 0}, zawodnicy[1]});
ll wnk = 1000000000000000000;
while (kolejka_dijsktra.size()) {
p4 = kolejka_dijsktra.top();
kolejka_dijsktra.pop();
p4.st.st = -p4.st.st;
if (dijkstra[p4.st.nd][p4.nd.st][p4.nd.nd] != -1) continue;
dijkstra[p4.st.nd][p4.nd.st][p4.nd.nd] = p4.st.st;
p1 = p4.nd;
//cout << "jestem w " << p4.st.st << " rodzaj " << p4.st.nd << " wspolrzedne " << p4.nd.st << " " << p4.nd.nd << "\n";
if (p4.st.nd == 0) {
for (pair<int, int> ele: ruchy) {
p2 = {p1.st + ele.st, p1.nd + ele.nd};
if (!dobre(p2)) continue;
if (dijkstra[p4.st.nd][p2.st][p2.nd] != -1) continue;
kolejka_dijsktra.push({{-(p4.st.st + c), 0}, {p2.st, p2.nd}});
}
f(i, 1, 5) {
if (dijkstra[i][p4.nd.st][p4.nd.nd] == -1) {
kolejka_dijsktra.push({{-(p4.st.st + b), i}, {p4.nd.st, p4.nd.nd}});
}
}
} else {
if (dijkstra[0][p4.nd.st][p4.nd.nd] == -1) kolejka_dijsktra.push({{-(p4.st.st + min_dojscie[p4.nd.st][p4.nd.nd]), 0}, {p4.nd.st, p4.nd.nd}});
p2 = p4.nd;
p2.st += ruchy[p4.st.nd - 1].st;
p2.nd += ruchy[p4.st.nd - 1].nd;
if (dobre(p2)) {
if (dijkstra[p4.st.nd][p2.st][p2.nd] == -1) {
kolejka_dijsktra.push({{-(p4.st.st + a), p4.st.nd}, {p2.st, p2.nd}});
//cout << "dodaje " << (p4.st.st + a) << " " << p4.st.nd << " " << p2.st << " " << p2.nd << "\n";
}
}
}
if (p4.nd.st == zawodnicy[n].st && p4.nd.nd == zawodnicy[n].nd) {wnk = p4.st.st; break;}
}
cout << wnk;
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... |