結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー furon
提出日時 2023-05-31 13:14:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,147 bytes
コンパイル時間 1,534 ms
コンパイル使用メモリ 134,408 KB
最終ジャッジ日時 2025-02-13 17:05:46
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 WA * 2 RE * 1
権限があれば一括ダウンロードができます

ソースコード

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