結果
問題 | No.17 2つの地点に泊まりたい |
ユーザー |
![]() |
提出日時 | 2015-05-21 05:36:37 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,995 bytes |
コンパイル時間 | 756 ms |
コンパイル使用メモリ | 74,996 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-06 04:19:57 |
合計ジャッジ時間 | 2,850 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 73 ms
6,940 KB |
testcase_04 | AC | 6 ms
6,944 KB |
testcase_05 | AC | 77 ms
6,940 KB |
testcase_06 | AC | 39 ms
6,940 KB |
testcase_07 | AC | 22 ms
6,940 KB |
testcase_08 | AC | 161 ms
6,940 KB |
testcase_09 | AC | 158 ms
6,940 KB |
testcase_10 | AC | 116 ms
6,940 KB |
testcase_11 | AC | 179 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 71 ms
6,944 KB |
testcase_24 | AC | 121 ms
6,944 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 147 ms
6,944 KB |
ソースコード
#include <iostream> #include <vector> #include <limits> #include <algorithm> #include <queue> using namespace std; struct Node { Node(int distance, int node) : distance(distance), node(node) {} int distance; int node; }; struct DistanceGreater : binary_function < Node, Node, bool > { bool operator()(const Node& lhs, const Node& rhs) const { return lhs.distance > rhs.distance; } }; int shortest(const vector<vector<int> >& costs, size_t start, size_t end) { size_t n = costs.size(); vector<int> distance(n, numeric_limits<int>::max()); distance[start] = 0; priority_queue<Node, vector<Node>, DistanceGreater> undetermined; undetermined.push(Node(distance[start], start)); vector<bool> determined(n, false); while (!undetermined.empty()) { Node node = undetermined.top(); undetermined.pop(); determined[node.node] = true; for (size_t adjNode = 0; adjNode < n; ++adjNode) { if (determined[adjNode]) { continue; } int cost = costs[node.node][adjNode]; if (cost == numeric_limits<int>::max()) { continue; } int newDistance = distance[node.node] + cost; if (newDistance < distance[adjNode]) { distance[adjNode] = newDistance; undetermined.push(Node(newDistance, adjNode)); } } } return distance[end]; } int main() { int n; cin >> n; vector<int> s(n); for (int i = 0; i < n; ++i) { cin >> s[i]; } vector<vector<int> > costs(n, vector<int>(n, numeric_limits<int>::max())); int m; cin >> m; for (int i = 0; i < m; ++i) { int a, b, c; cin >> a >> b >> c; costs[a][b] = c; costs[b][a] = c; } int minCost = numeric_limits<int>::max(); for (int stay1 = 1; stay1 <= n - 2; ++stay1) { for (int stay2 = 1; stay2 <= n - 2; ++stay2) { if (stay1 == stay2) { continue; } int cost = s[stay1] + s[stay2]; cost += shortest(costs, 0, stay1); cost += shortest(costs, stay1, stay2); cost += shortest(costs, stay2, n - 1); minCost = min(minCost, cost); } } cout << minCost << endl; return 0; }