結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー firiexp
提出日時 2019-10-19 17:39:33
言語 C++17(gcc12)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,186 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 911 ms
コンパイル使用メモリ 110,692 KB
最終ジャッジ日時 2026-03-08 21:44:48
合計ジャッジ時間 1,265 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:58:19: error: variable ‘std::array<int, 4> dy’ has initializer but incomplete type
   58 |     array<int, 4> dy{1, -1, 0, 0}, dx{0, 0, -1, 1};
      |                   ^~
main.cpp:58:36: error: variable ‘std::array<int, 4> dx’ has initializer but incomplete type
   58 |     array<int, 4> dy{1, -1, 0, 0}, dx{0, 0, -1, 1};
      |                                    ^~
main.cpp:54:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   54 |             scanf("%d", &c[i+1][j+1]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template <typename T>
struct edge {
    int from, to; T cost;
    edge(int to, T cost) : from(-1), to(to), cost(cost) {}
    edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
};

template <typename T>
vector<T> dijkstra(int s,vector<vector<edge<T>>> &G){
    auto n = G.size();
    vector<T> d(n, INF<T>);
    priority_queue<pair<T, int>,vector<pair<T, int>>,greater<>> Q;
    d[s] = 0;
    Q.emplace(0, s);
    while(!Q.empty()){
        T cost; int i;
        tie(cost, i) = Q.top(); Q.pop();
        if(d[i] < cost) continue;
        for (auto &&e : G[i]) {
            auto cost2 = cost + e.cost;
            if(d[e.to] <= cost2) continue;
            d[e.to] = cost2;
            Q.emplace(d[e.to], e.to);
        }
    }
    return d;
}

int main() {
    int n, v, ox, oy;
    cin >> n >> v >> ox >> oy;
    ox--; oy--;
    vector<vector<int>> c(n+2, vector<int>(n+2, INF<int>));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &c[i+1][j+1]);
        }
    }
    vector<vector<edge<int>>> G(n*n);
    array<int, 4> dy{1, -1, 0, 0}, dx{0, 0, -1, 1};
    auto f = [&](int i, int j){ return i*n+j; };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < 4; ++k) {
                if(f(i+dy[k], j+dx[k]) >= 0 && f(i+dy[k], j+dx[k]) < n*n){
                    G[f(i, j)].emplace_back(f(i+dy[k], j+dx[k]), c[i+dy[k]+1][j+dx[k]+1]);
                }
            }
        }
    }
    auto dist = dijkstra(0, G);
    if(dist.back() < v){
        puts("YES");
        return 0;
    }
    if(ox == -1){
        puts("NO");
        return 0;
    }
    auto dist2 = dijkstra(f(oy, ox), G);
    if(v-dist[f(oy, ox)] > 0 && dist2.back() < (v-dist[f(oy, ox)])*2){
        puts("YES");
    }else puts("NO");
    return 0;
}
0