Submission #1181043

#TimeUsernameProblemLanguageResultExecution timeMemory
1181043miniobSoccer (JOI17_soccer)C++20
0 / 100
652 ms22892 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...