Submission #1198653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198653		niepamietamhasla	Soccer (JOI17_soccer)	C++20	100 / 100	469 ms	38684 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];


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

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

ll odl2[MAXN][MAXN][5];

struct g{
    int a;
    int b;
    int c;
    ll koszt;
};

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

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

void dijkstra(pair<int,int> st){
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= m; ++j){
            for(int k = 0; k < 5; ++k){
                odl2[i][j][k] = -1;
            }
        }
    }
    pq.push({st.first, st.second, 0, 0});
    while(!pq.empty()){
        auto e = pq.top();
        pq.pop();
        if(odl2[e.a][e.b][e.c] != -1) continue;
        odl2[e.a][e.b][e.c] = e.koszt;
        if(e.c == 0){
            if(e.a > 0 and odl2[e.a-1][e.b][0] == -1){
                pq.push((g){e.a-1,e.b,0, e.koszt + C});
            }
            if(e.a < n and odl2[e.a+1][e.b][0] == -1){
                pq.push((g){e.a+1,e.b,0,e.koszt+C});
            }
            if(e.b > 0 and odl2[e.a][e.b-1][0] == -1){
                pq.push((g){e.a,e.b-1,0,e.koszt+C});
            }
            if(e.b < m and odl2[e.a][e.b+1][0] == -1){
                pq.push((g){e.a,e.b+1,0,e.koszt+C});
            }


            if(e.a > 0 and odl2[e.a-1][e.b][1] == -1){
                pq.push((g){e.a-1,e.b,1,e.koszt+A+B});
            }
            if(e.a < n and odl2[e.a+1][e.b][3] == -1){
                pq.push((g){e.a+1,e.b,3,e.koszt+A+B});
            }
            if(e.b > 0 and odl2[e.a][e.b-1][4] == -1){
                pq.push((g){e.a,e.b-1,4,e.koszt+A+B});
            }
            if(e.b < m and odl2[e.a][e.b+1][2] == -1){
                pq.push((g){e.a,e.b+1,2,e.koszt+A+B});
            }

        }
        else{
            pq.push((g){e.a,e.b,0,e.koszt+C*odl[e.a][e.b]});
            if(e.c == 4){
                if(e.b > 0 and odl2[e.a][e.b-1][4] == -1){
                    pq.push((g){e.a,e.b-1,4,e.koszt+A});
                }
            }
            else if(e.c == 1){
                if(e.a > 0 and odl2[e.a-1][e.b][1] == -1){
                    pq.push((g){e.a-1,e.b,1,e.koszt+A});
                }
            }
            else if(e.c == 3){
                if(e.a < n and odl2[e.a+1][e.b][3] == -1){
                    pq.push((g){e.a+1,e.b,3,e.koszt+A});
                }
            }
            else{
                if(e.b < m and odl2[e.a][e.b+1][2] == -1){
                    pq.push((g){e.a,e.b+1,2,e.koszt+A});
                }
            }
        }
    }
    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);
    ll t = 1e18;
    for(int i = 0; i < 5; ++i){
        if(odl2[koniec.first][koniec.second][i] != -1) t = min(t, odl2[koniec.first][koniec.second][i]);
    }
    cout << t << "\n";
    return 0;
}

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