Submission #1195383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195383		niepamietamhasla	Soccer (JOI17_soccer)	C++20	0 / 100	229 ms	327680 KiB

soccer

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

ll n, m, A, B, C;
int k;
int x, y;

struct d{
    int a;
    int b;
    ll koszt;
};

const int MAXN = 505;

queue<d> q;
ll odl[MAXN][MAXN][2];

struct e{
    int a;
    int b;
    int kt;
    ll koszt;
};

vector<e> graf[MAXN][MAXN][2];


void bfs(){
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= m; ++j){
            odl[i][j][0] = -1;
        }
    }
    while(!q.empty()){
        auto e = q.front();
        q.pop();
        if(odl[e.a][e.b][0] != -1) continue;
        odl[e.a][e.b][0] = e.koszt;
        if(e.a > 0 and odl[e.a-1][e.b][0] == -1){
            q.push({e.a - 1, e.b, e.koszt + 1});
        }
        if(e.a < n and odl[e.a+1][e.b][0] == -1){
            q.push({e.a + 1, e.b, e.koszt + 1});

        }
        if(e.b > 0 and odl[e.a][e.b-1][0] == -1){
            q.push({e.a, e.b - 1, e.koszt + 1});
        }
        if(e.b < m and odl[e.a][e.b+1][0] == -1){
            q.push({e.a, e.b + 1, e.koszt + 1});
        }
    }
    return;
}

struct comp{
    bool operator()(const e &e1, const e &e2) const {
        if(e1.koszt != e2.koszt) return e1.koszt > e2.koszt;
        return false;
    }
};

priority_queue<e, vector<e>, comp> pq;

void dijkstra(pair<int,int> st){
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= m; ++j){
            odl[i][j][0] = -1;
            odl[i][j][1] = -1;
        }
    }
    pq.push({st.first, st.second, 0, 0});
    pq.push({st.first, st.second, 1, 0});
    while(!pq.empty()){
        auto u = pq.top();
        pq.pop();
        if(odl[u.a][u.b][u.kt] != -1) continue;
        odl[u.a][u.b][u.kt] = u.koszt;
        for(auto f : graf[u.a][u.b][u.kt]){
            if(odl[f.a][f.b][f.kt] != -1) continue;
            pq.push({f.a, f.b, f.kt, f.koszt + u.koszt});
        }
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    cin >> A >> B >> C;
    cin >> k;
    pair<int,int> start;
    pair<int,int> koniec;
    for(int i = 0; i < k; ++i){
        cin >> x >> y;
        if(i == 0) start = {x,y};
        if(i == k-1) koniec = {x,y};
        q.push({x, y, 0});
    }
    bfs();
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= m; ++j){
            for(int l = 0; l <= n; ++l){
                if(l == i) continue;
                graf[i][j][0].push_back({l, j, 0, C * abs(l - i)});
                graf[i][j][0].push_back({l, j, 1, B + A * abs(l - i)});
                graf[i][j][1].push_back({l, j, 0, C * abs(l - i) + C * odl[i][j][0]});
                graf[i][j][1].push_back({l, j, 1, C * odl[i][j][0] + B + A * abs(l - i)});
            }
            for(int l = 0; l <= m; ++l){
                if(l == j) continue;
                graf[i][j][0].push_back({i, l, 0, C * abs(l - j)});
                graf[i][j][0].push_back({i, l, 1, B + A * abs(l - j)});
                graf[i][j][1].push_back({i, l, 0, C * abs(l - j) + C * odl[i][j][0]});
                graf[i][j][1].push_back({i, l, 1, C * odl[i][j][0] + B + A * abs(l - j)});
            }
        }
    }
    dijkstra(start);
    cout << min(odl[koniec.first][koniec.second][0], odl[koniec.first][koniec.second][1]) << "\n";
    return 0;
}

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