結果

問題 No.20 砂漠のオアシス
ユーザー atn112323atn112323
提出日時 2017-01-02 21:20:10
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 1,362 bytes
コンパイル時間 624 ms
コンパイル使用メモリ 66,900 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-13 05:45:18
合計ジャッジ時間 1,304 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

const int DX[4] = {1, 0, -1, 0};
const int DY[4] = {0, 1, 0, -1};
const int INF = 1000000;

int N, V, OX, OY;
int L[202][202];
int dist[202][202];

void bfs(int sx, int sy) {
	for (int i = 0; i < N + 2; i++) {
		for (int j = 0; j < N + 2; j++) {
			dist[i][j] = V + 1;
		}
	}
	priority_queue<pair<int, int> > P;
	P.push(make_pair(0, sx + sy * (N + 2)));
	dist[sx][sy] = 0;
	while (!P.empty()) {
		pair<int, int> p = P.top();
		P.pop();
		int x = p.second % (N + 2), y = p.second / (N + 2);
		if (-p.first > dist[x][y]) {
			continue;
		}
		for (int d = 0; d < 4; d++) {
			int xx = x + DX[d], yy = y + DY[d];
			if (dist[x][y] + L[xx][yy] < dist[xx][yy]) {
				dist[xx][yy] = dist[x][y] + L[xx][yy];
				P.push(make_pair(-dist[xx][yy], xx + yy * (N + 2)));
			}
		}
	}
}

int main() {
	cin >> N >> V >> OX >> OY;
	for (int i = 0; i < N + 2; i++) {
		for (int j = 0; j < N + 2; j++) {
			L[i][j] = INF;
		}
	}
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> L[x + 1][y + 1];
		}
	}
	bfs(1, 1);
	if (dist[N][N] < V) {
		cout << "YES" << endl;
	} else if (dist[OX][OY] < V) {
		V -= dist[OX][OY];
		V *= 2;
		bfs(OX, OY);
		if (dist[N][N] < V) {
			cout << "YES" << endl;
		} else {
			cout << "NO" << endl;
		}
	} else {
		cout << "NO" << endl;
	}
	return 0;
}
0