結果

問題 No.20 砂漠のオアシス
ユーザー atn112323
提出日時 2016-05-06 11:51:15
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,365 bytes
コンパイル時間 535 ms
コンパイル使用メモリ 67,068 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-13 05:37:00
合計ジャッジ時間 1,537 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 WA * 2
権限があれば一括ダウンロードができます

ソースコード

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