結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー Kutimoti_T
提出日時 2017-12-18 17:39:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 558 ms / 5,000 ms
コード長 2,375 bytes
コンパイル時間 689 ms
コンパイル使用メモリ 67,788 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-16 00:13:21
合計ジャッジ時間 2,729 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;

#define FOR(i, s, e) for (int i = (s); i <= (e); i++)

#define INF 1000000;

int N, V;

int Ox, Oy;

int L[210][210];

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int dp[210][210];
int dp2[210][210];

int main()
{
    FOR(i, 0, 209)
    {
        FOR(j, 0, 209)
        {
            dp[i][j] = INF;
            dp2[i][j] = INF;
        }
    }
    cin >> N >> V;
    cin >> Ox >> Oy;
    FOR(i, 1, N)
    {
        FOR(j, 1, N)
        {
            cin >> L[j][i];
        }
    }
    dp[1][1] = 0;

    while (true)
    {
        bool update = false;

        FOR(i, 1, N)
        {
            FOR(j, 1, N)
            {
                FOR(k, 0, 3)
                {
                    int x = i + dx[k];
                    int y = j + dy[k];

                    if (1 <= x && x <= N && 1 <= y && y <= N)
                    {
                        if (dp[x][y] > dp[i][j] + L[x][y])
                        {
                            dp[x][y] = dp[i][j] + L[x][y];
                            update = true;
                        }
                    }
                }
            }
        }
        if (update == false)
            break;
    }

    if (Ox != 0 && Oy != 0)
    {
        dp2[Ox][Oy] = 0;
        while (true)
        {
            bool update = false;
            FOR(i, 1, N)
            {
                FOR(j, 1, N)
                {
                    FOR(k, 0, 3)
                    {
                        int x = i + dx[k];
                        int y = j + dy[k];

                        if (1 <= x && x <= N && 1 <= y && y <= N)
                        {
                            if (dp2[x][y] > dp2[i][j] + L[x][y])
                            {
                                dp2[x][y] = dp2[i][j] + L[x][y];
                                update = true;
                            }
                        }
                    }
                }
            }
            if(update == false) break;
        }
    }

    if (dp[N][N] < V)
        cout << "YES" << endl;
    else if (Ox != 0 && Oy != 0 && ((V - dp[Ox][Oy]) * 2 - dp2[N][N] > 0))
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}
0