結果

問題 No.20 砂漠のオアシス
ユーザー data9824data9824
提出日時 2015-06-12 05:26:57
言語 C++11
(gcc 11.4.0)
結果
MLE  
実行時間 -
コード長 3,425 bytes
コンパイル時間 674 ms
コンパイル使用メモリ 74,140 KB
実行使用メモリ 816,128 KB
最終ジャッジ日時 2024-04-21 06:32:21
合計ジャッジ時間 2,747 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 28 ms
26,880 KB
testcase_04 AC 32 ms
28,800 KB
testcase_05 MLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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 vector<vector<int> >& costs, int startNode, int endNode) {
	size_t nodeCount = costs.size();
	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;
		for (size_t adjNode = 0; adjNode < nodeCount; ++adjNode) {
			if (determined[adjNode]) {
				continue;
			}
			int cost = costs[shortestNode][adjNode];
			if (cost == numeric_limits<int>::max()) {
				continue;
			}
			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;
	vector<vector<int> > costs(nodeCount, vector<int>(nodeCount, numeric_limits<int>::max()));
	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];
			}
		}
	}
	int startNode = index(n, 0);
	costs[startNode][index(0, 0)] = l[0][0];
	int endNode = index(n, 1);
	costs[index(n - 1, n - 1)][endNode] = l[n - 1][n - 1];
	int minCost = shortest(costs, startNode, endNode);
	bool possible = false;
	if (minCost < v * 2) {
		possible = true;
	}
	if (!possible && ox != 0 && oy != 0) {
		costs[index(n - 1, n - 1)][endNode] = numeric_limits<int>::max();
		costs[index(ox, oy)][endNode] = l[ox][oy];
		int toOasisCost = shortest(costs, startNode, endNode);
		if (toOasisCost < v * 2) {
			int regainedEnergy = (v * 2 - toOasisCost) * 2;
			costs[startNode][index(0, 0)] = numeric_limits<int>::max();
			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)][endNode] = numeric_limits<int>::max();
			costs[index(n - 1, n - 1)][endNode] = l[n - 1][n - 1];
			int fromOasisCost = shortest(costs, startNode, endNode);
			if (fromOasisCost < regainedEnergy) {
				possible = true;
			}
		}
	}
	cout << (possible ? "YES" : "NO") << endl;
	return 0;
}
0