結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー pessimist
提出日時 2026-01-18 02:05:45
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 57 ms / 5,000 ms
コード長 1,756 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,500 ms
コンパイル使用メモリ 357,192 KB
実行使用メモリ 15,744 KB
最終ジャッジ日時 2026-01-18 02:05:51
合計ジャッジ時間 5,428 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
void solve(){
    int N,V,Ox,Oy;
    cin>>N>>V>>Oy>>Ox;
    --Ox,--Oy;
    vector<int> L(N*N);
    for(int i=0;i<N*N;++i)cin>>L[i];
    const int oasis=Ox*N+Oy;
    const int START=0;
    const int GOAL=N*N-1;
    vector<unordered_set<int>> g(N*N);
    for(int i=0;i<N*N;++i){
        auto [x,y]=pair(i/N,i%N);
        if(x){
            const int j=i-N;
            g[i].emplace(j);
            g[j].emplace(i);
        }
        if(y){
            const int j=i-1;
            g[i].emplace(j);
            g[j].emplace(i);
        }
    }

    auto dijkstra=[&](ll src){
        const ll INF=1e10+10;
        vector<ll> dist(N*N,INF);
        dist[src]=0;
        priority_queue<ll,vector<ll>,greater<ll>> pq;
        pq.emplace(src);
        const int mask=(1<<20)-1;
        while(!pq.empty()){
            auto s=pq.top(); pq.pop();
            auto [dv,v]=pair(s>>20,s&mask);
            if(dist[v]<dv)continue;
            for(auto&w:g[v]){
                const ll dw=dv+L[w];
                if(dw<dist[w]){
                    dist[w]=dw;
                    pq.emplace((dw<<20)+w);
                }
            }
        }
        return dist;
    };

    auto ANS=[&](bool val){
        if(val)cout<<"YES";
        else cout<<"NO";
    };

    auto dist1=dijkstra(START);
    if(dist1[GOAL]<V)return ANS(1);
    if(Ox==-1)return ANS(0);
    auto dist2=dijkstra(oasis);
    V-=dist1[oasis];V<<=1;
    if(V<=dist2[GOAL])return ANS(0);
    ANS(1);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int T=1; //cin>>T;
    while(T--)solve();
    return 0;
}
0