Yukicoder020 砂漠のオアシス

問題概要

二次元グリッド上に砂漠と、一点のみにオアシスがある。 砂漠に行くと$L[i]$だけ体力が減り、オアシスに到達すると残った体力が2倍になる。 体力が0になると死亡するとして、 始点$(Ox,Oy)$から終点$(N,N)$に無事にたどり着くことができるか。

$N\leqq10^2$、$V\leqq5*10^2$、$L(x,y)\leqq9$

yukicoder020

解法

一回もオアシスに行かないときはただのダイクストラでゴールに到達するために減る最小の体力を求めれば良い。
一回オアシスに寄るときはオアシスでのこった体力を2倍にして、オアシスを始点にしたときの終点までの最短距離がわかれば判定ができる。

計算量:$O(N^2log(N^2))$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    const int INF = 1e9;                          const LL LINF = 1e16;
    int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
    
    LL N;
    
    LL ans = 0LL;
    
    VVI dijkstra(int sy, int sx, VVI& cost) {
        int n = SZ(cost);
        using tp = tuple<int, int, int>;
        priority_queue<tp, vector<tp>, greater<tp>>pq;
        VVI dist(n, VI(n, INF));
        pq.push(tp(0, sy, sx));
        dist[sy][sx] = 0;
        while (!pq.empty()) {
            int d, y, x; tie(d, y, x) = pq.top(); pq.pop();
            if (dist[y][x] < d)continue;
            FOR(k, 0, 4) {
                int ny = y + DY[k], nx = x + DX[k];
                if (0 <= ny&& ny < n && 0 <= nx && nx < n) {
                    if (dist[ny][nx] > dist[y][x] + cost[ny][nx]) {
                        dist[ny][nx] = dist[y][x] + cost[ny][nx];
                        pq.push(tp(dist[ny][nx], ny, nx));
                    }
                }
            }
        }
        return dist;
    }
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int V, oy, ox;
        cin >> N >> V >> ox >> oy;
        oy--, ox--;
        VVI cost(N, VI(N));
        FOR(i, 0, N) {
            FOR(j, 0, N) {
                cin >> cost[i][j];
            }
        }
        VVI dist = dijkstra(0, 0, cost);
        if (dist[N - 1][N - 1] < V) {
            cout << "YES" << endl;
        }
        else if (oy == -1 && dist[N - 1][N - 1] >= V) {
            cout << "NO" << endl;
        }
        else {
            int recover = 2 * (V - dist[oy][ox]);
            VVI ndist = dijkstra(oy, ox, cost);
            if (ndist[N - 1][N - 1] < recover) {
                cout << "YES" << endl;
            }
            else {
                cout << "NO" << endl;
            }
        }
    
        return 0;
    }