結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー ゴリポン先生
提出日時 2025-06-11 10:56:21
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 30 ms / 5,000 ms
コード長 1,977 bytes
コンパイル時間 6,767 ms
コンパイル使用メモリ 240,588 KB
実行使用メモリ 9,100 KB
最終ジャッジ日時 2025-06-11 10:56:29
合計ジャッジ時間 3,853 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// https://yang33-kassa.jp/yukicoder/yukicoder020/ より
// 2次元グリッド、ダイクストラ法
import std;

int N, V, Oy, Ox;
immutable INF = 10 ^^ 9;

// C++ の tie
auto tie(StoreElements...)(ref StoreElements stores)
{
	alias Elements = staticMap!(Unqual, StoreElements);
	
	template toPointer(T)
	{
		alias toPointer = T*;
	}
	
	struct Holder
	{
		alias StoreElementsPtrs = staticMap!(toPointer, StoreElements);
		StoreElementsPtrs storePtrs;
		
		this(ref StoreElements stores)
		{
			foreach(i, _; StoreElements)
			{
				storePtrs[i] = &stores[i];
			}
		}
		
		void opAssign(Tuple!Elements values)
		{
			foreach(i, _; Elements)
			{
				*storePtrs[i] = values[i];
			}
		}
	}
	
	return Holder(stores);
}
auto dir = [[0, 1], [0, -1], [1, 0], [-1, 0]];
int[][] dijkstra(int sy, int sx, int[][] cost)
{
	alias T = Tuple!(int, int, int);
	auto dist = uninitializedArray!(int[][])(N, N);
	foreach (ref row; dist)
		row[] = INF;
	dist[sy][sx] = 0;
	auto que = redBlackTree!("a[0] < b[0]", true, T)(T(0, sy, sx));
	while (!que.empty) {
		int d, y, x;
		tie(d, y, x) = que.front;
		que.removeFront;
		if (dist[y][x] < d) continue;
		foreach (di; dir) {
			int ny = y + di[0], nx = x + di[1];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (dist[ny][nx] > dist[y][x] + cost[ny][nx]) {
				dist[ny][nx] = dist[y][x] + cost[ny][nx];
				que.insert(T(dist[ny][nx], ny, nx));
			}
		}
	}
	return dist;
}

void main()
{
	// 入力
	readln.chomp.formattedRead("%d %d %d %d", N, V, Ox, Oy);
	--Oy, --Ox;
	auto cost = new int[][](N);
	foreach (ref row; cost) {
		row = readln.split.to!(int[]);
	}
	// 答えの計算と出力
	auto dist = dijkstra(0, 0, cost);
	if (dist[N - 1][N - 1] < V) {
		writeln("YES");
		return;
	}
	if (Oy == -1 && dist[N - 1][N - 1] >= V) {
		writeln("NO");
		return;
	}
	int recover = 2 * (V - dist[Oy][Ox]);
	dist = dijkstra(Oy, Ox, cost);
	if (dist[N - 1][N - 1] < recover)
		writeln("YES");
	else
		writeln("NO");
}
0