Submission #1066252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066252		sammyuri	Soccer (JOI17_soccer)	C++17	35 / 100	2573 ms	262144 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dist[505][505];
ll dist_2[505][505];
ll a, b, c;

ll calc_cost(ll dx, ll dy) {
    ll best = (dx + dy) * c;
    best = min(best, dx * c + b + dy * a);
    best = min(best, dy * c + b + dx * a);
    return best;
}

int main() {
    memset(dist, -1, sizeof(dist));
    int h, w; cin >> h >> w;
    h ++; w ++;
    cin >> a >> b >> c;
    vector<pair<int, int>> players;
    int n; cin >> n;
    int starti, startj, endi, endj;
    for (int i = 0; i < n; i ++) {
        int s, t; cin >> s >> t;
        players.push_back({s, t});
        if (i == 0)
            starti = s, startj = t;
        else if (i == n - 1)
            endi = s, endj = t;
    }
    // multisource bfs
    queue<pair<int, int>> q;
    for (auto a : players) {
        dist[a.first][a.second] = 0;
        q.push(a);
    }
    while (q.size()) {
        pair<int, int> cur = q.front(); q.pop();
        int curdist = dist[cur.first][cur.second];
        if (cur.first > 0 && dist[cur.first - 1][cur.second] == -1) {
            q.push({cur.first - 1, cur.second});
            dist[cur.first - 1][cur.second] = curdist + 1;
        }
        if (cur.first < h - 1 && dist[cur.first + 1][cur.second] == -1) {
            q.push({cur.first + 1, cur.second});
            dist[cur.first + 1][cur.second] = curdist + 1;
        }
        if (cur.second > 0 && dist[cur.first][cur.second - 1] == -1) {
            q.push({cur.first, cur.second - 1});
            dist[cur.first][cur.second - 1] = curdist + 1;
        }
        if (cur.second < w - 1 && dist[cur.first][cur.second + 1] == -1) {
            q.push({cur.first, cur.second + 1});
            dist[cur.first][cur.second + 1] = curdist + 1;
        }
    }
    // calculate answer
    priority_queue<pair<ll, pair<int, int>>> pq;
    for (int i = 0; i < h; i ++)
        for (int j = 0; j < w; j ++) {
            // initial distance
            ll curdist = calc_cost(abs(i - starti), abs(j - startj));
            curdist += dist[i][j] * c;
            curdist = min(curdist, abs(i - starti) * c + abs(j - startj) * c);
            dist_2[i][j] = curdist;
            pq.push({-curdist, {i, j}});
        }
    ll best = 1e18;
    while (pq.size()) {
        auto cur = pq.top(); pq.pop();
        ll curdist = -cur.first;
        int i = cur.second.first, j = cur.second.second;
        if (dist_2[i][j] != curdist)
            continue;
        // send straight to finish
        // cout << curdist << " " << i << " " << j << endl;
        best = min(best, curdist + calc_cost(abs(i - endi), abs(j - endj)));
        for (int ii = 0; ii < h; ii ++) {
            ll newdist = curdist + calc_cost(abs(ii - i), 0) + dist[ii][j] * c;
            newdist = min(newdist, curdist + abs(ii - i) * c);
            if (dist_2[ii][j] > newdist) {
                dist_2[ii][j] = newdist;
                pq.push({-newdist, {ii, j}});
            }
        }
        for (int jj = 0; jj < w; jj ++) {
            ll newdist = curdist + calc_cost(abs(jj - j), 0) + dist[i][jj] * c;
            newdist = min(newdist, curdist + abs(jj - j) * c);
            if (dist_2[i][jj] > newdist) {
                dist_2[i][jj] = newdist;
                pq.push({-newdist, {i, jj}});
            }
        }
    }
    cout << best << endl;
    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:78:67: warning: 'endj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |         best = min(best, curdist + calc_cost(abs(i - endi), abs(j - endj)));
      |                                                                 ~~^~~~~~
soccer.cpp:78:52: warning: 'endi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |         best = min(best, curdist + calc_cost(abs(i - endi), abs(j - endj)));
      |                                                  ~~^~~~~~
soccer.cpp:23:17: warning: 'startj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |     int starti, startj, endi, endj;
      |                 ^~~~~~
soccer.cpp:23:9: warning: 'starti' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |     int starti, startj, endi, endj;
      |         ^~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 65