Submission #683154

#	Time	Username	Problem	Language	Result	Execution time	Memory
683154		Lobo	Soccer (JOI17_soccer)	C++17	100 / 100	508 ms	26500 KiB

soccer

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e5+10;
const int maxh = 505;

int h,w,A,B,C, fat[maxh][maxh], da[maxh][maxh][4], dc[maxh][maxh];
int n, s[maxn], t[maxn];
vector<pair<int,int>> adj = {mp(-1,0),mp(1,0),mp(0,1),mp(0,-1)};

void solve() {
    cin >> h >> w >> A >> B >> C;
    cin >> n;
    for(int i = 0; i <= h; i++) {
        for(int j = 0; j <= w; j++) {
            fat[i][j] = inf;
            da[i][j][0] = da[i][j][1] = da[i][j][2] = da[i][j][3] = dc[i][j] = inf;
        }
    }
    
    queue<pair<int,int>> q;
    for(int i = 1; i <= n; i++) {
        cin >> s[i] >> t[i];
        fat[s[i]][t[i]] = 0;
        q.push(mp(s[i],t[i]));
    }

    while(q.size()) {
        int i = q.front().fr;
        int j = q.front().sc;
        q.pop();
        for(auto X : adj) {
            int i1 = i+X.fr;
            int j1 = j+X.sc;
            if(i1 < 0 || j1 < 0 || i1 > h || j1 > w) continue;
            if(fat[i1][j1] == inf) {
                fat[i1][j1] = fat[i][j]+C;
                q.push(mp(i1,j1));
            }
        }
    } 

    priority_queue<pair<pair<int,pair<int,int>>,pair<int,int>>,vector<pair<pair<int,pair<int,int>>,pair<int,int>>>,greater<pair<pair<int,pair<int,int>>,pair<int,int>>>> pq;
    dc[s[1]][t[1]] = 0;
    pq.push(mp(mp(0,mp(1,0)),mp(s[1],t[1])));
    while(pq.size()) {
        int dist = pq.top().fr.fr;
        int tp = pq.top().fr.sc.fr;
        int tpa = pq.top().fr.sc.sc;
        int i = pq.top().sc.fr;
        int j = pq.top().sc.sc;
        pq.pop();
        if(tp == 0) {
            if(da[i][j][tpa] != dist) continue;
            auto X = adj[tpa];
            int i1 = i+X.fr;
            int j1 = j+X.sc;
            if(!(i1 < 0 || j1 < 0 || i1 > h || j1 > w) && da[i1][j1][tpa] > da[i][j][tpa]+A) {
                da[i1][j1][tpa] = da[i][j][tpa]+A;
                pq.push(mp(mp(da[i1][j1][tpa],mp(0,tpa)),mp(i1,j1)));
            }

            if(fat[i][j] == 0 && dc[i][j] > da[i][j][tpa]) {
                dc[i][j] = da[i][j][tpa];
                pq.push(mp(mp(dc[i][j],mp(1,0)),mp(i,j)));
            }
            if(dc[i][j] > da[i][j][tpa]+fat[i][j]) {
                dc[i][j] = da[i][j][tpa]+fat[i][j];
                pq.push(mp(mp(dc[i][j],mp(1,0)),mp(i,j)));
            }
        }
        else {
            if(dc[i][j] != dist) continue;
            for(auto X : adj) {
                int i1 = i+X.fr;
                int j1 = j+X.sc;
                if(i1 < 0 || j1 < 0 || i1 > h || j1 > w) continue;
                if(dc[i1][j1] > dc[i][j]+C) {
                    dc[i1][j1] = dc[i][j]+C;
                    pq.push(mp(mp(dc[i1][j1],mp(1,0)),mp(i1,j1)));
                }
            }

            for(int dir = 0; dir <= 3; dir++) {
                if(da[i][j][dir] > dc[i][j]+B) {
                    da[i][j][dir] = dc[i][j]+B;
                    pq.push(mp(mp(da[i][j][dir],mp(0,dir)),mp(i,j)));
                }
            }
        }
    }

    cout << dc[s[n]][t[n]] << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

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