結果

問題 No.20 砂漠のオアシス
ユーザー Unbakedbread
提出日時 2025-09-20 15:32:24
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,181 bytes
コンパイル時間 3,153 ms
コンパイル使用メモリ 288,524 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-09-20 15:32:29
合計ジャッジ時間 4,501 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

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

int main(void) {
	int N, V, ox, oy;
	cin >> N >> V >> ox >> oy;
	--ox, --oy;
	vector L(N, vector<int>(N));
	for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) cin >> L[i][j];
	
	auto dijk = [&](int sx, int sy) {
		vector d(N, vector<int>(N, 1e9));
		d[sx][sy] = 0;
		priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> que;
		que.push(make_tuple(0, sx, sy));
		
		while(!que.empty()) {
			auto [_, x, y] = que.top();
			que.pop();
			if(_ != d[x][y]) continue;
			for(int dir = 0; dir < 4; ++dir) {
				int nx = x + DX[dir], ny = y + DY[dir];
				if(0 <= nx and nx < N and 0 <= ny and ny < N and d[nx][ny] > d[x][y] + L[nx][ny]) {
					d[nx][ny] = d[x][y] + L[nx][ny];
					que.push(make_tuple(d[nx][ny], nx, ny));
				}
			}
		}
		
		return d;
	};
	
	auto d1 = dijk(0, 0);
	
	if(V - d1[N - 1][N - 1] > 0) {
		cout << "YES" << endl;
		return 0;
	}
	
	if(ox == -1 or V - d1[ox][oy] <= 0) {
		cout << "NO" << endl;
		return 0;
	}
	
	auto d2 = dijk(ox, oy);
	
	cout << ((V - d1[ox][oy]) * 2 - d2[N - 1][N - 1] > 0 ? "YES" : "NO") << endl;
	return 0;
}
0