#876245 (C++17) No.20 砂漠のオアシス

• 問題: No.20 砂漠のオアシス
• ユーザー: furon
• 提出日時: 2023-05-31 13:34:17
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 20 ms / 5,000 ms
• コード長: 2,144 bytes
• コンパイル時間: 1,362 ms
• コンパイル使用メモリ: 138,692 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-08 21:03:39
• 合計ジャッジ時間: 2,138 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	3 ms; 5,376 KB
testcase_05	AC	18 ms; 5,376 KB
testcase_06	AC	19 ms; 5,376 KB
testcase_07	AC	20 ms; 5,376 KB
testcase_08	AC	13 ms; 5,376 KB
testcase_09	AC	20 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	3 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	3 ms; 5,376 KB
testcase_15	AC	3 ms; 5,376 KB
testcase_16	AC	5 ms; 5,376 KB
testcase_17	AC	4 ms; 5,376 KB
testcase_18	AC	5 ms; 5,376 KB
testcase_19	AC	5 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB

ソースコード

#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;

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] = 0;
	pq.push({ sx, sy, 0 });
	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 (oy == -1) {
		cout << "NO" << endl;
		return 0;
	}
	if (cost[oy][ox] >= v) {
		cout << "NO" << endl;
		return 0;
	}

	v = (v - cost[oy][ox]) * 2;
	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;
}