Submission #651043

#	Time	Username	Problem	Language	Result	Execution time	Memory
651043		Ronin13	Soccer (JOI17_soccer)	C++14	0 / 100	566 ms	63576 KiB

soccer

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;


pii mov[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
const int NMAX = 501;
ll d[NMAX][NMAX];
ll D[NMAX][NMAX][4][2];

int main(){
    int h, w; cin >> h >> w;
    ll a, b, c; cin >> a >> b >> c;
    h++; w++;
    int n; cin >> n;
    int x[n + 1], y[n + 1];
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        x[i]++;
        y[i]++;
    }
    for(int i = 1; i <= h; ++i){
        for(int j = 1; j <= w; j++){
            d[i][j] = 1e9;
            for(int x = 0; x < 4; x++){
                for(int y = 0; y < 2; y++) D[i][j][x][y] = 1e18;
            }
        }
    }
    queue <pii> q;
    for(int i = 1; i <= n - 1; i++){
        d[x[i]][y[i]] = 0;
        q.push({x[i], y[i]});
    }
    while(!q.empty()){
        int x = q.front().f, y = q.front().s;
        q.pop();
        if(x > 1 && d[x - 1][y] == 1e9) d[x - 1][y] = d[x][y] + 1, q.push({x - 1, y});
        if(x < h && d[x + 1][y] == 1e9) d[x + 1][y] = d[x][y] + 1, q.push({x + 1, y});
        if(y > 1 && d[x][y - 1] == 1e9) d[x][y - 1] = d[x][y] + 1, q.push({x, y - 1});
        if(y < w && d[x][y + 1] == 1e9) d[x][y + 1] = d[x][y] + 1, q.push({x, y + 1});
     }
     /*for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++) cout << d[i][j] << ' ';
        cout << "\n";
     }*/
    set <pair<ll, pair<pii, pii> > > st;
    D[x[1]][y[1]][0][0] = 0;
    st.insert({0, {{x[1], y[1]}, {0, 0}}});
    while(!st.empty()){
        pair<ll, pair<pii, pii> > cur = *st.begin();
        st.erase(st.begin());
        ll x = cur.s.f.f, y = cur.s.f.s;
        int ind = cur.s.s.s, dir = cur.s.s.f;
        if(ind == 1){
            pii nn = mov[dir];
            int nx = x + nn.f;
            int ny = y + nn.s;
            if(nx > 0 && nx <= h && ny > 0 && ny <= w){
                if(D[nx][ny][dir][ind] > cur.f + a){
                    st.erase({D[nx][ny][dir][ind], {{nx, ny}, {dir, ind}}});
                    D[nx][ny][dir][ind] = cur.f + a;
                    st.insert({D[nx][ny][dir][ind], {{nx, ny}, {dir, ind}}});
                }
            }
            if(D[x][y][0][0] > cur.f + d[x][y] * c){
                st.erase({D[x][y][0][0], {{x, y}, {0, 0}}});
                D[x][y][0][0] = cur.f + d[x][y] * c;
                st.insert({D[x][y][0][0], {{x, y}, {0, 0}}});
            }
        }
        if(ind == 0){
            for(int j = 0; j < 4; j++){
                int nx = x + mov[j].f, ny = y + mov[j].s;
                if(nx > 0 && nx <= h && ny > 0 && ny <= w){
                    if(D[nx][ny][0][0] > cur.f + c){
                        st.erase({D[nx][ny][0][0], {{nx, ny}, {0, 0}}});
                        D[nx][ny][0][0] = cur.f + c;
                        st.insert({D[nx][ny][0][0], {{nx, ny}, {0, 0}}});
                    }
                }
                if(D[x][y][j][1] > cur.f + b){
                    st.erase({D[x][y][j][1], {{x, y}, {j, 1}}});
                    D[x][y][j][1] = D[x][y][0][0] + b;
                    st.insert({D[x][y][j][1], {{x, y}, {j, 1}}});
                }
            }
        }
    }
    ll ans = D[x[n]][y[n]][0][0];
    for(int i = 0; i < 4; i++){
        ans = min(D[x[n]][y[n]][i][1], ans);
    }
    cout << ans;
    return 0;
}

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