Submission #127189

#	Time	Username	Problem	Language	Result	Execution time	Memory
127189		EntityIT	Soccer (JOI17_soccer)	C++14	100 / 100	693 ms	21276 KiB

soccer

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second

using ii = pair<int, int>;
using ll = long long;
const int H = 505, W = H, N = (int)1e5 + 5;
const ll infll = (ll)1e18 + 123;
int h, w, a, b, c, n, s[N], t[N], mn[H][W], dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
ll dp[H][W][6];
/*
    0, 1, 2, 3: direction;
    4: carried;
    5: not carried;
*/

struct State {
    int x, y, sta;
    State (int _x = 0, int _y = 0, int _sta = 0) : x(_x), y(_y), sta(_sta) {}
    bool operator< (const State &_) const { return make_pair(x, make_pair(y, sta) ) < make_pair(_.x, make_pair(_.y, _.sta) ); }
};

bool validCell (int x, int y) { return x >= 0 && y >= 0 && x <= h && y <= w; }

void bfs () {
    memset(mn, -1, sizeof mn);
    queue<ii> q;
    for (int i = 1; i <= n; ++i) {
        mn[ s[i] ][ t[i] ] = 0;
        if (i != n) q.push( { s[i], t[i] } );
    }
    while (!q.empty() ) {
        int x = q.front().fi, y = q.front().se; q.pop();
        for (int _ = 0; _ < 4; ++_) {
            int nX = x + dx[_], nY = y + dy[_];
            if (validCell(nX, nY) && mn[nX][nY] == -1) {
                mn[nX][nY] = mn[x][y] + 1;
                q.push( { nX, nY } );
            }
        }
    }
}

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> h >> w >> a >> b >> c >> n;
    for (int i = 1; i <= n; ++i) cin >> s[i] >> t[i];

    bfs();

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            for (int k = 0; k < 6; ++k) dp[i][j][k] = infll;
        }
    }

    priority_queue<pair<ll, State>, vector< pair<ll, State> >, greater< pair<ll, State> > > pq;
    dp[ s[1] ][ t[1] ][4] = 0; pq.push( { dp[ s[1] ][ t[1] ][4], State(s[1], t[1], 4) } );
    while (!pq.empty() ) {
        auto tmp = pq.top(); pq.pop();
        int x = tmp.se.x, y = tmp.se.y, sta = tmp.se.sta;
        if (tmp.fi > dp[x][y][sta]) continue ;
        if (sta == 5) {
            if (dp[x][y][4] > dp[x][y][sta] + 1LL * c * mn[x][y]) {
                dp[x][y][4] = dp[x][y][sta] + 1LL * c * mn[x][y];
                pq.push( { dp[x][y][4], State(x, y, 4) } );
            }
        }
        else if (sta == 4) {
            for (int _ = 0; _ < 4; ++_) {
                int nX = x + dx[_], nY = y + dy[_];
                if (!validCell(nX, nY) ) continue ;
                if (dp[nX][nY][4] > dp[x][y][sta] + c) {
                    dp[nX][nY][4] = dp[x][y][sta] + c;
                    pq.push( { dp[nX][nY][4], State(nX, nY, 4) } );
                }
                if (dp[nX][nY][_] > dp[x][y][sta] + a + b) {
                    dp[nX][nY][_] = dp[x][y][sta] + a + b;
                    pq.push( { dp[nX][nY][_], State(nX, nY, _) } );
                }
            }
        }
        else {
            int nX = x + dx[sta], nY = y + dy[sta];
            if (validCell(nX, nY) ) {
                if (dp[nX][nY][sta] > dp[x][y][sta] + a) {
                    dp[nX][nY][sta] = dp[x][y][sta] + a;
                    pq.push( { dp[nX][nY][sta], State(nX, nY, sta) } );
                }
            }
            if (dp[x][y][5] > dp[x][y][sta]) {
                dp[x][y][5] = dp[x][y][sta];
                pq.push( { dp[x][y][5], State(x, y, 5) } );
            }
        }
    }

    cout << dp[ s[n] ][ t[n] ][4];

    return 0;
}

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