結果

問題 No.20 砂漠のオアシス
ユーザー furonfuron
提出日時 2023-05-31 13:14:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,147 bytes
コンパイル時間 2,834 ms
コンパイル使用メモリ 137,440 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-28 01:30:26
合計ジャッジ時間 4,549 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <random>

using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vpdd = vector<pdd>;
const int inf = (1 << 30) - 1;
const ll INF = 1LL << 60;
const int MOD = 1000000007;
//const int MOD = 998244353;

//#include <functional>
struct Point {
	int x, y;
	ll c;
	bool operator>(const Point& right) const {
		return c == right.c ? x > right.x : c > right.c;
	}
};

const int dy[4] = { -1,0,1,0 };
const int dx[4] = { 0,1,0,-1 };

void dijkstra2d(const vvi& g, int h, int w, int sy, int sx, vvl& cost) {
	cost.assign(h, vl(w, INF));

	priority_queue<Point, vector<Point>, greater<Point>> pq;
	cost[sy][sx] = g[sy][sx];
	pq.push({ sy, sx, g[sy][sx] });
	while (!pq.empty()) {
		Point p = pq.top();
		pq.pop();

		for (int i = 0; i < 4; i++) {
			int y2 = p.y + dy[i];
			int x2 = p.x + dx[i];
			if (y2 < 0 || y2 > h - 1 || x2 < 0 || x2 > w - 1) continue;

			ll c = p.c + g[y2][x2];
			if (cost[y2][x2] > c) {
				cost[y2][x2] = c;

				pq.push({ x2, y2, c });
			}
		}
	}
}


int main() {
	int n, v, ox, oy;
	cin >> n >> v >> ox >> oy;
	ox--; oy--;
	vvi g(n, vi(n));
	int h = n, w = n;
	for (int y = 0; y < h; y++) {
		for (int x = 0; x < w; x++) {
			cin >> g[y][x];
		}
	}
	vvl cost;
	dijkstra2d(g, h, w, 0, 0, cost);
	if (cost[h - 1][w - 1] < v) {
		cout << "YES" << endl;
		return 0;
	}

	if (cost[oy][ox] >= v) {
		cout << "NO" << endl;
		return 0;
	}
	
	v = (v - cost[oy][ox]) * 2;
	g[oy][ox] = 0;
	vvl cost2;
	dijkstra2d(g, h, w, oy, ox, cost2);

	if (cost2[h - 1][w - 1] < v) cout << "YES" << endl;
	else cout << "NO" << endl;
	
	return 0;
}
0