結果

問題 No.20 砂漠のオアシス
ユーザー ser00
提出日時 2017-12-11 20:51:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,920 bytes
コンパイル時間 907 ms
コンパイル使用メモリ 81,316 KB
実行使用メモリ 13,636 KB
最終ジャッジ日時 2024-11-30 08:53:52
合計ジャッジ時間 58,343 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 3 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct Item {
    int x;
    int y;
    int cost;

    bool operator<(const Item& rhs) const {
        return cost < rhs.cost;
    }
};

int DIR_X[] = {-1,  1,  0,  0};
int DIR_Y[] = { 0,  0,  1, -1};

typedef vector<vector<int> > cost_matrix_t;

cost_matrix_t dijkstra(int field[][200], int sx, int sy, int len_x, int len_y) {
    auto queue = priority_queue<Item>();

    auto costmatrix = vector<vector<int>>(len_x, vector<int>(len_y, INT_MAX));

    queue.push(Item{sx,sy,0});
    costmatrix[sx][sy] = 0;

    while(!queue.empty()) {
        Item item = queue.top();
        queue.pop();

        if(item.cost <= costmatrix[item.x][item.y]) {
            for(int i=0; i<4; i++) {
                int nx = item.x + DIR_X[i];
                if(nx<0 || len_x<=nx) continue;
                int ny = item.y + DIR_Y[i];
                if(ny<0 || len_y<=ny) continue;

                int c = item.cost + field[nx][ny];
                if(c<costmatrix[nx][ny]) {
                    costmatrix[nx][ny] = c;
                    queue.push(Item{nx,ny,c});
                }
            }
        }

    }

    return costmatrix;
}

int main() {

    int len, life, ox, oy;
    scanf("%d%d%d%d", &len, &life, &ox, &oy);
    ox--;
    oy--;

    int field[200][200];
    for(int i=0; i<len; i++) {
        for(int j=0; j<len; j++) {
            scanf("%d", &field[i][j]);
        }
    }

    cost_matrix_t c = dijkstra(field, 0, 0, len, len);
    if(c[len-1][len-1] < life) {
        printf("YES");

    } else if(ox>0 || oy>0) {
        cost_matrix_t c2 = dijkstra(field, ox, oy, len, len);
        if((life - c[ox][oy])*2 - c2[len-1][len-1] > 0) {
            printf("YES");
        } else {
            printf("NO");
        }
    } else {
        printf("NO");
    }

    return 0;
}
0