結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー data9824
提出日時 2015-06-13 06:08:48
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,615 bytes
コンパイル時間 1,180 ms
コンパイル使用メモリ 94,944 KB
実行使用メモリ 14,976 KB
最終ジャッジ日時 2024-10-13 05:12:46
合計ジャッジ時間 2,251 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <limits>
#include <queue>
#include <map>

using namespace std;

int n;

int index(int x, int y) {
	return x + y * (n + 1);
}

struct Node {
	Node(int distance, int node) : distance(distance), node(node) {}
	int distance;
	int node;
};
bool operator<(const Node& lhs, const Node& rhs) {
	return lhs.distance > rhs.distance;
}
int shortest(const map<int, map<int, int> >& costs, int nodeCount, int startNode, int endNode) {
	vector<int> distance(nodeCount, numeric_limits<int>::max());
	distance[startNode] = 0;
	priority_queue<Node> shortests;
	shortests.push(Node(distance[startNode], startNode));
	vector<bool> determined(nodeCount, false);
	while (!shortests.empty()) {
		Node edge = shortests.top();
		shortests.pop();
		determined[edge.node] = true;
		int shortestNode = edge.node;
		map<int, map<int, int> >::const_iterator itCosts = costs.find(shortestNode);
		if (itCosts == costs.end()) {
			continue;
		}
		for (map<int, int>::const_iterator it = itCosts->second.begin();
			it != itCosts->second.end();
			++it) {
			int adjNode = it->first;
			if (determined[adjNode]) {
				continue;
			}
			int cost = it->second;
			int newDistance = distance[shortestNode] + cost;
			if (newDistance < distance[adjNode]) {
				distance[adjNode] = newDistance;
				shortests.push(Node(newDistance, adjNode));
			}
		}
	}
	return distance[endNode];
}

int main() {
	int v, ox, oy;
	cin >> n >> v >> ox >> oy;
	vector<vector<int> > l(n, vector<int>(n));
	for (int y = 0; y < n; ++y) {
		for (int x = 0; x < n; ++x) {
			cin >> l[x][y];
		}
	}
	int nodeCount = (n + 1) * n;
	map<int, map<int, int> > costs;
	for (int y = 0; y < n; ++y) {
		for (int x = 0; x < n; ++x) {
			if (x < n - 1) {
				costs[index(x, y)][index(x + 1, y)] = l[x][y];
				costs[index(x + 1, y)][index(x, y)] = l[x][y];
			}
			if (x > 0) {
				costs[index(x, y)][index(x - 1, y)] += l[x][y];
				costs[index(x - 1, y)][index(x, y)] += l[x][y];
			}
			if (y < n - 1) {
				costs[index(x, y)][index(x, y + 1)] = l[x][y];
				costs[index(x, y + 1)][index(x, y)] = l[x][y];
			}
			if (y > 0) {
				costs[index(x, y)][index(x, y - 1)] += l[x][y];
				costs[index(x, y - 1)][index(x, y)] += l[x][y];
			}
		}
	}
	costs[index(0, 0)][index(1, 0)] = 0;
	costs[index(1, 0)][index(0, 0)] = 0;
	costs[index(0, 0)][index(0, 1)] = 0;
	costs[index(0, 1)][index(0, 0)] = 0;
	int startNode = index(n, 0);
	int endNode = index(n, 1);
	costs[startNode][index(0, 0)] = 0;
	costs[index(n - 1, n - 1)][endNode] = l[n - 1][n - 1];
	int minCost = shortest(costs, nodeCount, startNode, endNode);
	bool possible = false;
	if (minCost < v * 2) {
		possible = true;
	}
	if (!possible && ox != 0 && oy != 0) {
		--ox;
		--oy;
		costs[index(n - 1, n - 1)].erase(endNode);
		costs[index(ox, oy)][endNode] = l[ox][oy];
		int toOasisCost = shortest(costs, nodeCount, startNode, endNode);
		if (toOasisCost < v * 2) {
			int regainedEnergy = (v * 2 - toOasisCost) * 2;
			costs[startNode].erase(index(0, 0));
			if (ox < n - 1) {
				costs[startNode][index(ox + 1, oy)] = l[ox + 1][oy];
			}
			if (ox > 0) {
				costs[startNode][index(ox - 1, oy)] = l[ox - 1][oy];
			}
			if (oy < n - 1) {
				costs[startNode][index(ox, oy + 1)] = l[ox][oy + 1];
			}
			if (oy > 0) {
				costs[startNode][index(ox, oy - 1)] = l[ox][oy - 1];
			}
			costs[index(ox, oy)].erase(endNode);
			costs[index(n - 1, n - 1)][endNode] = l[n - 1][n - 1];
			int fromOasisCost = shortest(costs, nodeCount, startNode, endNode);
			if (fromOasisCost < regainedEnergy) {
				possible = true;
			}
		}
	}
	cout << (possible ? "YES" : "NO") << endl;
	return 0;
}
0