結果

問題 No.1473 おでぶなおばけさん
ユーザー cutmdocutmdo
提出日時 2024-07-19 00:10:49
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 672 ms / 2,000 ms
コード長 3,572 bytes
コンパイル時間 1,309 ms
コンパイル使用メモリ 109,932 KB
実行使用メモリ 21,308 KB
最終ジャッジ日時 2024-07-19 00:11:08
合計ジャッジ時間 15,725 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 523 ms
20,360 KB
testcase_03 AC 402 ms
17,300 KB
testcase_04 AC 384 ms
12,612 KB
testcase_05 AC 109 ms
6,280 KB
testcase_06 AC 448 ms
19,908 KB
testcase_07 AC 592 ms
21,252 KB
testcase_08 AC 672 ms
21,300 KB
testcase_09 AC 544 ms
21,308 KB
testcase_10 AC 119 ms
12,160 KB
testcase_11 AC 117 ms
14,336 KB
testcase_12 AC 121 ms
13,312 KB
testcase_13 AC 70 ms
9,216 KB
testcase_14 AC 50 ms
7,680 KB
testcase_15 AC 96 ms
11,776 KB
testcase_16 AC 108 ms
11,776 KB
testcase_17 AC 10 ms
5,376 KB
testcase_18 AC 16 ms
5,376 KB
testcase_19 AC 137 ms
10,688 KB
testcase_20 AC 250 ms
15,948 KB
testcase_21 AC 224 ms
15,120 KB
testcase_22 AC 217 ms
18,664 KB
testcase_23 AC 209 ms
16,672 KB
testcase_24 AC 185 ms
16,184 KB
testcase_25 AC 531 ms
18,468 KB
testcase_26 AC 554 ms
18,728 KB
testcase_27 AC 170 ms
9,376 KB
testcase_28 AC 440 ms
20,968 KB
testcase_29 AC 252 ms
16,328 KB
testcase_30 AC 340 ms
18,452 KB
testcase_31 AC 401 ms
20,864 KB
testcase_32 AC 326 ms
18,504 KB
testcase_33 AC 264 ms
15,792 KB
testcase_34 AC 144 ms
10,008 KB
testcase_35 AC 125 ms
9,488 KB
testcase_36 AC 219 ms
14,656 KB
testcase_37 AC 291 ms
15,672 KB
testcase_38 AC 52 ms
6,024 KB
testcase_39 AC 111 ms
11,904 KB
testcase_40 AC 111 ms
11,904 KB
testcase_41 AC 97 ms
12,244 KB
testcase_42 AC 95 ms
12,112 KB
testcase_43 AC 210 ms
16,940 KB
testcase_44 AC 214 ms
16,940 KB
testcase_45 AC 207 ms
16,944 KB
testcase_46 AC 390 ms
15,828 KB
testcase_47 AC 458 ms
18,652 KB
testcase_48 AC 342 ms
17,292 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/no/1473"

#include <iostream>
#include <vector>
#include <queue>
#include <vector>
#include <deque>
#include <tuple>

template<class Node = int, class Cost = long long>
class Graph {
    //using Node = int;
    //using Cost = long long;

    using Edge = std::pair<Node, Cost>;
    using Edges = std::vector<Edge>;

    const int m_n;
    std::vector<Edges> m_graph;

public:
    Graph(int n) :m_n(n), m_graph(n) {}

    auto addEdge(const Node& f, const Node& t, const Cost& c = 1) {
        m_graph[f].emplace_back(t, c);
    }
    auto addEdgeUndirected(const Node& f, const Node& t, const Cost& c = 1) {
        addEdge(f, t, c); addEdge(t, f, c);
    }
    auto getEdges(const Node& from)const {
        class EdgesRange {
            const typename Edges::const_iterator b, e;
        public:
            EdgesRange(const Edges& edges) :b(edges.begin()), e(edges.end()) {}
            auto begin()const { return b; }
            auto end()const { return e; }
        };
        return EdgesRange(m_graph[from]);
    }
    auto getEdges()const {
        std::deque<std::tuple<Node, Node, Cost>> edges;
        for(Node from = 0; from < m_n; ++from) for(const auto& [to, c] : getEdges(from)) {
            edges.emplace_back(from, to, c);
        }
        return edges;
    }
    auto getEdgesExcludeCost()const {
        std::deque<std::pair<Node, Node>> edges;
        for(Node from = 0; from < m_n; ++from) for(const auto& [to, _] : getEdges(from)) {
            edges.emplace_back(from, to);
        }
        return edges;
    }
    auto reverse()const {
        auto rev = Graph<Node, Cost>(m_n);
        for(const auto& [from, to, c] : getEdges()) {
            rev.addEdge(to, from, c);
        }
        return rev;
    }
    auto size()const { return m_n; };
    auto debug(bool directed = false)const {
        for(const auto& [f, t, c] : getEdges())if(f < t || directed) {
            std::cout << f << " -> " << t << ": " << c << std::endl;
        }
    }
};
template <class Lambda>
auto binarySearch(long long ok, long long ng, const Lambda& is_ok) {
    while(std::abs(ok - ng) > 1) {
        long long mid = (ok + ng) >> 1;
        (is_ok(mid) ? ok : ng) = mid;
    }
    return ok;
}
template<class Node, class Cost, class Lambda>
auto bfs(const Graph<Node, Cost>& graph, const Node& root, const Lambda& lambda) {
    auto n = graph.size();
    std::vector<bool> used(n); used[root] = true;
    std::queue<Node> q; q.emplace(root);
    while(!q.empty()) {
        auto from = q.front();
        q.pop();
        for(const auto& [to, _] : graph.getEdges(from)) {
            if(used[to]) { continue; }
            q.emplace(to);
            used[to] = true;
            lambda(from, to);
        }
    }
}

using ll = long long;
using std::cout;
using std::cin;
constexpr char endl = '\n';

signed main() {
    ll n, m;
    cin >> n >> m;
    auto graph_all = Graph(n);
    for(int i = 0; i < m; ++i) {
        ll s, t, d;
        cin >> s >> t >> d;
        graph_all.addEdgeUndirected(s - 1, t - 1, d);
    }

    auto solve = [&](ll w) {
        auto graph = Graph(n);
        for(const auto& [s, t, d] : graph_all.getEdges()) {
            if(w <= d) { graph.addEdge(s, t); }
        }

        std::vector<int> dv(n);
        bfs(graph, 0, [&](ll f, ll t) {dv[t] = dv[f] + 1; });
        return dv[n - 1];
    };

    auto w_max = binarySearch(0, 1e9 + 1, [&](ll w) {
        auto d = solve(w);
        return d > 0;
    });

    auto ans = solve(w_max);
    cout << w_max << " " << ans << endl;
}
0