Yukicoder034 砂漠の行商人

問題概要

二次元グリッドのマスに砂漠があり、ここに入ると$L(x,y)$のダメージを受ける。 体力$V$で、始点から体力が0より大きくかつ最短時間で終点に行きたい。 どれだけの時間がかかるか。

$N\leqq10^2$、$V\leqq10^5$、$0≦L(x,y)\leqq9$

yukicoder034

解法

時間を最短距離とみたグラフについて、体力の状態もさまざまなので、体力ごとに頂点を作成する。 ただし辺のコストが1なのでBFSになる。 $dist(y,x,v)$:=体力が$v$で点$(y,x)$にいるときの最小時間として計算する。

別解としてDPの添字と目的値を変更するアレで、 $dist(距離,y,x)$:=必要な最小体力とすると速いらしい。

計算量:$O(VN^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 };
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        LL N, V; cin >> N >> V;
        int sy, sx, ty, tx; cin >> sx >> sy >> tx >> ty;
        sy--, sx--, tx--, ty--;
        VVI cost(N, VI(N));
        FOR(i, 0, N) {
            FOR(j, 0, N) {
                cin >> cost[i][j];
            }
        }
        using tp = tuple<int, int, int, int>;
        queue<tp>pq;
        vector<VVI>dist(N, VVI(N, VI(V, INF)));
        dist[sy][sx][V - 1] = 0;
        pq.push(tp(0, V - 1, sy, sx));
    
        while (!pq.empty()) {
            int d, v, y, x;
            tie(d, v, y, x) = pq.front(); pq.pop();
            if (dist[y][x][v] < d)continue;
            if (ty == y && tx == x) {
                cout << d << endl;
                return 0;
            }
            FOR(k, 0, 4) {
                int ny = y + DY[k], nx = x + DX[k];
                if (0 <= ny && ny < N && 0 <= nx && nx < N) {
                    int nv = v - cost[ny][nx];
                    if (nv >= 0) {
                        if (dist[ny][nx][nv] > dist[y][x][v] + 1) {
                            dist[ny][nx][nv] = dist[y][x][v] + 1;
                            pq.push(tp(dist[ny][nx][nv], nv, ny, nx));
                        }
                    }
                }
            }
    
        }
    
        cout << -1 << "\n";
    
        return 0;
    }