Submission #114212

#	Time	Username	Problem	Language	Result	Execution time	Memory
114212		popovicirobert	Soccer (JOI17_soccer)	C++14	100 / 100	523 ms	21244 KiB

soccer

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const ll INF = 1e18;
vector < vector <ll> > dst_c;

int dl[] = {-1, 0, 1, 0}, dc[] = {0, -1, 0, 1};

vector <int> x, y;
int h, w, A, B, C, n;

inline bool in(int l, int c) {
    return l >= 0 && c >= 0 && l <= h && c <= w;
}

inline void bfs() {
    queue < pair <int, int> > Q;

    dst_c.resize(h + 1, vector <ll>(w + 1, INF));

    for(int i = 1; i < n; i++) {
        dst_c[x[i]][y[i]] = 0;
        Q.push({x[i], y[i]});
    }

    while(Q.size()) {
        auto cur = Q.front();
        Q.pop();

        for(int i = 0; i < 4; i++) {
            int l = cur.first + dl[i];
            int c = cur.second + dc[i];

            if(in(l, c) && dst_c[l][c] == INF) {
                dst_c[l][c] = dst_c[cur.first][cur.second] + C;
                Q.push({l, c});
            }
        }

    }
}

struct Data {
    int l, c, t;
    ll cst;

    bool operator <(const Data &other) const {
        return cst > other.cst;
    }
};

const int MAXH = 500;

ll dst[MAXH + 1][MAXH + 1][5];
bool vis[MAXH + 1][MAXH + 1][5];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> h >> w >> A >> B >> C >> n;

    x.resize(n + 1), y.resize(n + 1);
    for(i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    bfs();

    priority_queue <Data> pq;

    for(i = 0; i <= h; i++) {
        for(j = 0; j <= w; j++) {
            for(int d = 0; d < 5; d++) {
                dst[i][j][d] = INF;
            }
        }
    }

    pq.push({x[1], y[1], 4, 0});
    dst[x[1]][y[1]][4] = 0;

    while(pq.size()) {
        auto cur = pq.top();
        pq.pop();

        if(vis[cur.l][cur.c][cur.t]) {
            continue;
        }

        vis[cur.l][cur.c][cur.t] = 1;

        if(cur.t != 4) {
            ll cst = cur.cst + B;

            if(cur.l != x[n] || cur.c != y[n]) {
                cst += dst_c[cur.l][cur.c];
            }

            if(dst[cur.l][cur.c][4] > cst) {
                dst[cur.l][cur.c][4] = cst;
                pq.push({cur.l, cur.c, 4, cst});
            }
        }

        if(cur.t == 4) {
            for(i = 0; i < 4; i++) {
                int l = cur.l + dl[i], c = cur.c + dc[i];

                if(in(l, c) && dst[l][c][4] > cur.cst + C) {
                    dst[l][c][4] = cur.cst + C;
                    pq.push({l, c, 4, dst[l][c][4]});
                }

                if(in(l, c) && dst[l][c][i] > cur.cst + A) {
                    dst[l][c][i] = cur.cst + A;
                    pq.push({l, c, i, dst[l][c][i]});
                }
            }
        }
        else {
            int l = cur.l + dl[cur.t], c = cur.c + dc[cur.t];

            if(in(l, c) && dst[l][c][cur.t] > cur.cst + A) {
                dst[l][c][cur.t] = cur.cst + A;
                pq.push({l, c, cur.t, dst[l][c][cur.t]});
            }
        }
    }

    cout << dst[x[n]][y[n]][4];

    //cin.close();
    //cout.close();
    return 0;
}

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