Submission #361255

#	Time	Username	Problem	Language	Result	Execution time	Memory
361255		jainbot27	Soccer (JOI17_soccer)	C++17	100 / 100	535 ms	21980 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