Submission #1195827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195827		niepamietamhasla	Soccer (JOI17_soccer)	C++20	0 / 100	440 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;
};

int odl2[MAXN][MAXN];

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

        }
        if(e.b > 0 and odl2[e.a][e.b-1] == -1){
            q.push({e.a, e.b - 1, e.koszt + 1});
        }
        if(e.b < m and odl2[e.a][e.b+1] == -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;
        //cout << u.a << " " << u.b << " " << u.kt << " " << u.koszt << " u\n";
        for(int l = 0; l <= n; ++l){
            if(l == u.a) continue;
            if(u.kt == 0){
            	if(odl[l][u.b][0] == -1) pq.push({l, u.b, 0, C * abs(l - u.a) + u.koszt});
            	if(odl[l][u.b][1] == -1) pq.push({l, u.b, 1, B + A * abs(l - u.a) + u.koszt});	
            }
            else{
            	if(odl[l][u.b][0] == -1) pq.push({l, u.b, 0, C * abs(l - u.a) + C * odl2[u.a][u.b] + u.koszt});
            	if(odl[l][u.b][1] == -1) pq.push({l, u.b, 1, C * odl2[u.a][u.b] + B + A * abs(l - u.a) + u.koszt});	
            }
        }
        for(int l = 0; l <= m; ++l){
            if(l == u.b) continue;
            if(u.kt == 0){
            	if(odl[u.a][l][0] == -1) pq.push({u.a, l, 0, C * abs(l - u.b) + u.koszt});
            	if(odl[u.a][l][1] == -1) pq.push({u.a, l, 1, B + A * abs(l - u.b) + u.koszt});	
            }
            else{
            	if(odl[u.a][l][0] == -1) pq.push({u.a, l, 0, C * abs(l - u.b) + C * odl2[u.a][u.b] + u.koszt});
            	if(odl[u.a][l][1] == -1) pq.push({u.a, l, 1, C * odl2[u.a][u.b] + B + A * abs(l - u.b) + 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();
    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