結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー hogeover30
提出日時 2015-04-14 02:36:56
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 26 ms / 5,000 ms
コード長 1,245 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,196 ms
コンパイル使用メモリ 175,556 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-08 16:02:05
合計ジャッジ時間 1,964 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
const int inf=10000000;
int L[210][210];
int dr[]={-1, 0, 1, 0}, dc[]={0, -1, 0, 1};
int n, v, ox, oy;

int dijkstra(int s, int t)
{
    priority_queue<pair<int, int>> q;
    vector<int> d(n*n, inf);
    d[s]=L[s/n][s%n];
    q.emplace(0, s);
    while (q.size()) {
        int cost, p;
        tie(cost, p)=q.top(); q.pop();
        cost=-cost;
        int r=p/n, c=p%n;
        if (cost>d[p]) continue;
        for(int i=0;i<4;++i) {
            int nr=r+dr[i], nc=c+dc[i];
            if (nr<0 or nr>=n or nc<0 or nc>=n) continue;
            int np=nr*n+nc;
            if (d[np]>cost+L[nr][nc]) {
                d[np]=cost+L[nr][nc];
                q.emplace(-d[np], np);
            }
        }
    }
    return d[t];
}


int main()
{
    while (cin>>n>>v>>ox>>oy) {
        for(int i=0;i<n;++i) for(int j=0;j<n;++j) cin>>L[i][j];
        if (dijkstra(0, n*n-1)<v)
            cout<<"YES";
        else if (ox and oy) {
            --ox, --oy;
            int x=dijkstra(0, oy*n+ox);
            int y=dijkstra(oy*n+ox, n*n-1);
            cout<<(v>x and (v-x)*2>y ? "YES" : "NO");
        }
        else
            cout<<"NO";
        cout<<endl;
    }
}
0