結果

問題 No.20 砂漠のオアシス
ユーザー spade630spade630
提出日時 2015-11-04 17:06:08
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 1,865 bytes
コンパイル時間 824 ms
コンパイル使用メモリ 79,728 KB
実行使用メモリ 4,388 KB
最終ジャッジ日時 2023-08-03 07:53:24
合計ジャッジ時間 1,718 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 17 ms
4,388 KB
testcase_06 AC 16 ms
4,376 KB
testcase_07 AC 18 ms
4,380 KB
testcase_08 AC 11 ms
4,380 KB
testcase_09 AC 17 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 4 ms
4,380 KB
testcase_15 AC 3 ms
4,384 KB
testcase_16 AC 4 ms
4,380 KB
testcase_17 AC 4 ms
4,376 KB
testcase_18 AC 4 ms
4,376 KB
testcase_19 AC 5 ms
4,380 KB
testcase_20 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <ctime>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FFOR(i,a,b) for(int i=(a);i<=(b);i++)
#define REP(i,b) FOR(i,0,b)
#define RREP(i,b) FFOR(i,1,b)
#define PB push_back
#define F first
#define S second
#define BE(c) c.begin(),c.end()
using namespace std;
typedef long long LL;
typedef LL ut;
typedef long double ld;
typedef pair<ut,ut> pr;
typedef vector<pr> Vpr;
typedef vector<ut> VI;
typedef pair<ut,pr> ppr;
typedef priority_queue<pr,Vpr, greater<pr> > PQ;
const int SIZE=1e+5 + 1;
const ut INF=1<<29;
const ld eps=1e-6;
const LL mod=1e+6 + 3;

int N, V, ox, oy;
int maze[256][256];
int d[256][256];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

bool check(int x, int y){
	return x >= 0 && x < N && y >= 0 && y < N;
}

void dijkstra(int sx, int sy){
	REP(i,N)REP(j,N)
		d[i][j] = INF;
	priority_queue<ppr, vector<ppr>, greater<ppr>> que;
	que.push(ppr(0, pr(sx, sy)));
	d[sy][sx] = 0;
	
	while(!que.empty()){
		ppr p = que.top(); que.pop();
		int x = p.S.F, y = p.S.S;
		if(d[y][x] < p.F)
			continue;
		REP(i,4){
			int nx = x + dx[i], ny = y + dy[i];
			if(check(nx, ny)){
				if(d[ny][nx] > d[y][x] + maze[ny][nx]){
					d[ny][nx] = d[y][x] + maze[ny][nx];
					que.push(ppr(d[ny][nx], pr(nx, ny)));
				}
			}
		}
	}	
}

int main() {
	cin >> N >> V >> ox >> oy;
	REP(i,N)REP(j,N){
		scanf("%d", &maze[i][j]);
	}
	dijkstra(0, 0);
	if(V - d[N - 1][N - 1] > 0){
		cout << "YES" << endl;
	}
	else if(ox + oy == 0 || V - d[oy - 1][ox - 1] <= 0){
		cout << "NO" << endl;
	}
	else{
		V = (V - d[oy - 1][ox - 1]) * 2;
		dijkstra(ox - 1, oy - 1);
		if(V - d[N - 1][N - 1] <= 0){
			cout << "NO" << endl;
		}
		else{
			cout << "YES" << endl;
		}
	}
 	return 0;
}
0