結果
問題 | No.34 砂漠の行商人 |
ユーザー | data9824 |
提出日時 | 2015-06-15 20:18:32 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 103 ms / 5,000 ms |
コード長 | 1,730 bytes |
コンパイル時間 | 972 ms |
コンパイル使用メモリ | 82,512 KB |
実行使用メモリ | 6,472 KB |
最終ジャッジ日時 | 2023-09-10 19:09:15 |
合計ジャッジ時間 | 2,270 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 9 ms
4,528 KB |
testcase_05 | AC | 9 ms
4,380 KB |
testcase_06 | AC | 4 ms
4,380 KB |
testcase_07 | AC | 23 ms
4,788 KB |
testcase_08 | AC | 29 ms
5,392 KB |
testcase_09 | AC | 34 ms
5,180 KB |
testcase_10 | AC | 11 ms
5,644 KB |
testcase_11 | AC | 13 ms
5,340 KB |
testcase_12 | AC | 4 ms
4,376 KB |
testcase_13 | AC | 103 ms
6,472 KB |
testcase_14 | AC | 70 ms
6,368 KB |
testcase_15 | AC | 3 ms
4,380 KB |
testcase_16 | AC | 8 ms
4,380 KB |
testcase_17 | AC | 5 ms
4,764 KB |
testcase_18 | AC | 2 ms
4,376 KB |
testcase_19 | AC | 28 ms
5,776 KB |
testcase_20 | AC | 40 ms
6,116 KB |
testcase_21 | AC | 72 ms
6,132 KB |
testcase_22 | AC | 6 ms
5,172 KB |
testcase_23 | AC | 4 ms
4,464 KB |
testcase_24 | AC | 49 ms
6,044 KB |
testcase_25 | AC | 6 ms
4,484 KB |
ソースコード
#include <iostream> #include <vector> #include <map> #include <queue> #include <limits> using namespace std; int n, v; struct Node { int node; int depth; int distance; Node(int node, int depth, int distance) : node(node), depth(depth), distance(distance) {} }; int shortest(const vector<map<int, int> >& costs, int nodeCount, int startNode, int endNode) { queue<Node> q; vector<int> distances(nodeCount, numeric_limits<int>::max()); q.push(Node(startNode, 0, 0)); while (!q.empty()) { Node node = q.front(); q.pop(); if (distances[node.node] > node.distance) { distances[node.node] = node.distance; if (node.node == endNode && node.distance < v) { return node.depth; } for (map<int, int>::const_iterator it = costs[node.node].begin(); it != costs[node.node].end(); ++it) { q.push(Node(it->first, node.depth + 1, node.distance + it->second)); } } } return -1; } int index(int x, int y) { return (x - 1) + (y - 1) * n; } int main() { int sx, sy, gx, gy; cin >> n >> v >> sx >> sy >> gx >> gy; vector<vector<int> > l(n + 1, vector<int>(n + 1)); for (int y = 1; y <= n; ++y) { for (int x = 1; x <= n; ++x) { cin >> l[x][y]; } } int nodeCount = n * n; vector<map<int, int> > edges(nodeCount); for (int y = 1; y <= n; ++y) { for (int x = 1; x <= n; ++x) { if (x > 1) { edges[index(x - 1, y)][index(x, y)] = l[x][y]; } if (x < n) { edges[index(x + 1, y)][index(x, y)] = l[x][y]; } if (y > 1) { edges[index(x, y - 1)][index(x, y)] = l[x][y]; } if (y < n) { edges[index(x, y + 1)][index(x, y)] = l[x][y]; } } } int result = shortest(edges, nodeCount, index(sx, sy), index(gx, gy)); cout << result << endl; return 0; }