結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー codershifth
提出日時 2015-07-20 19:34:21
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 24 ms / 5,000 ms
コード長 2,640 bytes
コンパイル時間 1,480 ms
コンパイル使用メモリ 173,408 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-13 05:20:46
合計ジャッジ時間 2,320 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;


class Oasis {
public:
    void solve(void) {
            int N,V,ox,oy;
            cin>>N>>V>>ox>>oy;
            --ox;
            --oy;
            vector<vector<int>> field(N,vector<int>(N,0));
            REP(i,N)
            {
                REP(j,N)
                    cin>>field[i][j];
            }
            const int inf = (1<<30);

            // V=N*N E=(N-1)*N*4
            // 3回 dijkstra をやればよい O(3*E*log(V))
            auto calcCost = [&](int sx, int sy, int gx, int gy) {
                vector<vector<int>> dist(N,vector<int>(N,inf));

                typedef tuple<int,int,int> P;
                priority_queue<P, vector<P>, greater<P>> que;
                que.emplace(0,sx,sy);
                dist[sy][sx] = 0;

                while (!que.empty())
                {
                    int x,y,d;
                    tie(d,x,y) = que.top();
                    que.pop();

                    if (dist[y][x] < d)
                        continue;

                    const int dx[] = {-1,0,1,0};
                    const int dy[] = {0,1,0,-1};
                    REP(d, 4)
                    {
                        int nx = x+dx[d];
                        int ny = y+dy[d];
                        if (nx < 0 || ny < 0 || N <= nx || N <= ny)
                            continue;
                        if (dist[y][x] + field[ny][nx] < dist[ny][nx])
                        {
                            dist[ny][nx] = dist[y][x] + field[ny][nx];
                            que.emplace(dist[ny][nx],nx,ny);
                        }
                    }
                }
                return dist[gy][gx];
            };
            int v1 = calcCost(0,0,N-1,N-1);
            if (V > v1)
            {
                cout<<"YES"<<endl;
                return;
            }
            else if (ox < 0 || oy < 0)
            {
                cout<<"NO"<<endl;
                return;
            }
            int v2 = calcCost(0,0,ox,oy);
            int v3 = calcCost(ox,oy,N-1,N-1);
            if (V-v2 > 0 && (V-v2)*2 > v3)
            {
                cout<<"YES"<<endl;
                return;
            }
            cout<<"NO"<<endl;
            return;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new Oasis();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0