結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー himueu
提出日時 2026-10-17 13:40:12
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 17 ms / 5,000 ms
+ 778µs
コード長 1,885 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,004 ms
コンパイル使用メモリ 201,804 KB
実行使用メモリ 9,772 KB
最終ジャッジ日時 2026-10-17 13:40:33
合計ジャッジ時間 5,029 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <queue>
#include <utility>
#include <vector>

int main() {
    using namespace std;
    int n, life, ox, oy;
    cin >> n >> life >> ox >> oy;
    vector L(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) { cin >> L[j][i]; }
    }
    int m = n * n;
    constexpr int dx[] = {-1, 0, 1, 0};
    constexpr int dy[] = {0, -1, 0, 1};
    vector<vector<pair<int, int>>> g(m);
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < n; y++) {
            int p = x * n + y;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) { continue; }
                int np = nx * n + ny;
                g[p].emplace_back(np, L[nx][ny]);
            }
        }
    }

    constexpr int INF = 1e9;
    auto dijkstra = [&](int start, vector<vector<pair<int, int>>> &g) -> vector<int> {
        int n = g.size();
        vector<int> res(n, INF);
        res[start] = 0;
        priority_queue<
            pair<int, int>,
            vector<pair<int, int>>,
            greater<pair<int, int>>> que;
        que.emplace(0, start);
        while (!que.empty()) {
            auto [c, v] = que.top();
            que.pop();
            if (res[v] < c) { continue; }
            for (auto [nv, w] : g[v]) {
                if (res[nv] > c + w) {
                    res[nv] = c + w;
                    que.emplace(c + w, nv);
                }
            }
        }
        return res;
    };

    bool ok = false;
    auto d0 = dijkstra(0, g);
    if (d0[m - 1] < life) { ok = true; }
    if (ox > 0 && oy > 0) {
        int p = (ox - 1) * n + (oy - 1);
        int rem_life = (life - d0[p]) * 2;
        auto dp = dijkstra(p, g);
        if (dp[m - 1] < rem_life) { ok = true; }
    }
    cout << (ok ? "YES\n" : "NO\n");
}
0