結果
問題 | No.1473 おでぶなおばけさん |
ユーザー | commy |
提出日時 | 2023-03-12 03:56:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,106 ms / 2,000 ms |
コード長 | 6,973 bytes |
コンパイル時間 | 2,587 ms |
コンパイル使用メモリ | 117,380 KB |
実行使用メモリ | 13,624 KB |
最終ジャッジ日時 | 2023-10-18 10:27:34 |
合計ジャッジ時間 | 20,691 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 900 ms
12,752 KB |
testcase_03 | AC | 439 ms
10,492 KB |
testcase_04 | AC | 379 ms
8,620 KB |
testcase_05 | AC | 88 ms
5,148 KB |
testcase_06 | AC | 454 ms
11,120 KB |
testcase_07 | AC | 982 ms
13,356 KB |
testcase_08 | AC | 1,106 ms
13,620 KB |
testcase_09 | AC | 989 ms
13,624 KB |
testcase_10 | AC | 40 ms
6,692 KB |
testcase_11 | AC | 39 ms
7,404 KB |
testcase_12 | AC | 40 ms
7,012 KB |
testcase_13 | AC | 24 ms
5,556 KB |
testcase_14 | AC | 18 ms
5,104 KB |
testcase_15 | AC | 33 ms
6,616 KB |
testcase_16 | AC | 38 ms
6,548 KB |
testcase_17 | AC | 5 ms
4,348 KB |
testcase_18 | AC | 7 ms
4,348 KB |
testcase_19 | AC | 55 ms
5,696 KB |
testcase_20 | AC | 197 ms
10,104 KB |
testcase_21 | AC | 138 ms
8,864 KB |
testcase_22 | AC | 95 ms
12,380 KB |
testcase_23 | AC | 79 ms
10,864 KB |
testcase_24 | AC | 78 ms
10,892 KB |
testcase_25 | AC | 874 ms
12,240 KB |
testcase_26 | AC | 842 ms
12,940 KB |
testcase_27 | AC | 159 ms
7,112 KB |
testcase_28 | AC | 696 ms
13,520 KB |
testcase_29 | AC | 249 ms
11,128 KB |
testcase_30 | AC | 432 ms
12,368 KB |
testcase_31 | AC | 558 ms
13,252 KB |
testcase_32 | AC | 262 ms
10,888 KB |
testcase_33 | AC | 230 ms
9,852 KB |
testcase_34 | AC | 105 ms
7,168 KB |
testcase_35 | AC | 71 ms
5,948 KB |
testcase_36 | AC | 234 ms
9,960 KB |
testcase_37 | AC | 352 ms
10,548 KB |
testcase_38 | AC | 42 ms
4,996 KB |
testcase_39 | AC | 38 ms
6,444 KB |
testcase_40 | AC | 38 ms
6,668 KB |
testcase_41 | AC | 34 ms
6,276 KB |
testcase_42 | AC | 34 ms
6,192 KB |
testcase_43 | AC | 165 ms
10,132 KB |
testcase_44 | AC | 166 ms
10,132 KB |
testcase_45 | AC | 167 ms
10,132 KB |
testcase_46 | AC | 499 ms
10,572 KB |
testcase_47 | AC | 748 ms
12,236 KB |
testcase_48 | AC | 684 ms
11,548 KB |
ソースコード
#include <algorithm> #include <iostream> #include <numeric> #include <string> #include <tuple> #include <utility> #include <vector> #include <limits> #define rep(i, a, b) for (int i = int(a); i < int(b); i++) using namespace std; using ll = long long int; // NOLINT using P = pair<ll, ll>; // clang-format off #ifdef _DEBUG_ #define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; debug_print(__VA_ARGS__); } while(false) template<typename T, typename... Ts> void debug_print(const T &t, const Ts &...ts) { cerr << t; ((cerr << ", " << ts), ...); cerr << endl; } #else #define dump(...) do{ } while(false) #endif template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); } template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); } template<typename T> bool chmin(T &a, const T& b) { if (a > b) {a = b; return true; } return false; } template<typename T> bool chmax(T &a, const T& b) { if (a < b) {a = b; return true; } return false; } template<typename T, typename... Ts> void print(const T& t, const Ts&... ts) { cout << t; ((cout << ' ' << ts), ...); cout << '\n'; } template<typename... Ts> void input(Ts&... ts) { (cin >> ... >> ts); } template<typename T> istream &operator,(istream &in, T &t) { return in >> t; } struct Inf { template<typename T> constexpr operator T() { return numeric_limits<T>::max() / 2; } }; // clang-format on #include <limits> #include <cmath> #include <queue> #include <deque> enum class CostType { NoEdge, One, ZeroOne, Plus, PlusMinus, }; template<typename Cost = long long, typename Vertex = int> class Graph { using Edge = pair<Cost, Vertex>; using ShortestInfo = pair<vector<Cost>, vector<Vertex>>; vector<vector<Edge>> g; CostType cost_type; ShortestInfo no_edge(Vertex s) { auto costs = vector<Cost>(g.size(), Inf); auto prev = vector<Vertex>(g.size(), None); costs[s] = 0; return make_pair(move(costs), move(prev)); } ShortestInfo bfs01(Vertex s) { auto [costs, prev] = no_edge(s); deque<Edge> deq; deq.emplace_back(0, s); while (deq.size()) { auto [c, v] = deq.front(); deq.pop_front(); if (costs[v] < c) continue; for (auto &&[nc, nv] : adjacent(v)) { if (costs[nv] > c + nc) { costs[nv] = c + nc; if (nc == 0) { deq.emplace_front(c, nv); } else { deq.emplace_back(c + 1, nv); } prev[nv] = v; } } } return make_pair(move(costs), move(prev)); } ShortestInfo bfs(Vertex s) { auto [costs, prev] = no_edge(s); queue<Edge> que; que.emplace(0, s); while (que.size()) { auto [c, v] = que.front(); que.pop(); if (costs[v] < c) continue; for (auto &&[nc, nv] : adjacent(v)) { if (costs[nv] > c + nc) { costs[nv] = c + nc; que.emplace(c + nc, nv); prev[nv] = v; } } } return make_pair(move(costs), move(prev)); } ShortestInfo dijkstra(Vertex s) { auto [costs, prev] = no_edge(s); priority_queue<Edge, vector<Edge>, greater<Edge>> pq; pq.emplace(0, s); while (pq.size()) { auto [c, v] = pq.top(); pq.pop(); if (costs[v] < c) continue; for (auto &&[nc, nv] : adjacent(v)) { if (costs[nv] > c + nc) { costs[nv] = c + nc; pq.emplace(c + nc, nv); prev[nv] = v; } } } return make_pair(move(costs), move(prev)); } ShortestInfo bellman_ford(Vertex s) { auto [costs, prev] = no_edge(s); for (size_t i = 0, n = g.size(); i < 2 * n; i++) { for (Vertex v = 0; v < static_cast<Vertex>(n); v++) { if (costs[v] == Inf) continue; for (auto &&[cost, nv] : adjacent(v)) { if (costs[v] == -Inf || costs[v] + cost < costs[nv]) { if (i >= n) { costs[nv] = -Inf; } else { costs[nv] = costs[v] + cost; } prev[nv] = v; } } } } return make_pair(move(costs), move(prev)); } void update_cost_type(Cost cost) { CostType ct = CostType::NoEdge; if (signbit(cost)) { ct = CostType::PlusMinus; } else if (cost != 0 && cost != 1) { ct = CostType::Plus; } else if (cost == 0) { ct = CostType::ZeroOne; } else if (cost == 1) { ct = CostType::One; } cost_type = static_cast<CostType>(max(static_cast<int>(ct), static_cast<int>(cost_type))); } public: Graph(size_t n) : g(n), cost_type(CostType::NoEdge) {} void add_edge(Vertex s, Vertex t, Cost cost) { update_cost_type(cost); g[s].emplace_back(cost, t); } const vector<Edge> &adjacent(Vertex v) const { return g[v]; } size_t size() const { return g.size(); } CostType get_cost_type() const { return cost_type; } ShortestInfo shortest(Vertex s) { switch (cost_type) { case CostType::ZeroOne: return bfs01(s); case CostType::One: return bfs(s); case CostType::Plus: return dijkstra(s); case CostType::PlusMinus: return bellman_ford(s); case CostType::NoEdge: return no_edge(s); } __builtin_unreachable(); } constexpr static Cost Inf = numeric_limits<Cost>::max(); constexpr static Vertex None = -1; }; using Edge = tuple<int, int, int>; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, m; cin >> n >> m; vector<Edge> edges(m); rep(i, 0, m) { int a, b, c; cin >> a >> b >> c; a--; b--; edges[i] = Edge(a, b, c); } int l = 0, r = 1e+9; int w = 0, c = 0; while (l <= r) { int mid = (l + r) / 2; Graph<> graph(n); for (auto [a, b, c] : edges) { if (c >= mid) { graph.add_edge(a, b, 1); graph.add_edge(b, a, 1); } } auto [cost, prev] = graph.shortest(0); if (cost[n - 1] == graph.Inf) { r = mid - 1; } else { w = mid; c = cost[n - 1]; l = mid + 1; } } print(w, c); return 0; }