#891935 (C++23) No.1320 Two Type Min Cost Cycle

• 問題: No.1320 Two Type Min Cost Cycle
• ユーザー: 👑 hitonanode
• 提出日時: 2023-07-15 20:46:26
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 353 ms / 2,000 ms
• コード長: 4,874 bytes
• コンパイル時間: 1,672 ms
• コンパイル使用メモリ: 133,028 KB
• 実行使用メモリ: 4,348 KB
• 最終ジャッジ日時: 2023-10-17 06:52:24
• 合計ジャッジ時間: 6,594 ms
• ジャッジサーバーID （参考情報）: judge13 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	2 ms; 4,348 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	2 ms; 4,348 KB
testcase_04	AC	2 ms; 4,348 KB
testcase_05	AC	2 ms; 4,348 KB
testcase_06	AC	3 ms; 4,348 KB
testcase_07	AC	10 ms; 4,348 KB
testcase_08	AC	11 ms; 4,348 KB
testcase_09	AC	241 ms; 4,348 KB
testcase_10	AC	13 ms; 4,348 KB
testcase_11	AC	190 ms; 4,348 KB
testcase_12	AC	33 ms; 4,348 KB
testcase_13	AC	98 ms; 4,348 KB
testcase_14	AC	7 ms; 4,348 KB
testcase_15	AC	13 ms; 4,348 KB
testcase_16	AC	4 ms; 4,348 KB
testcase_17	AC	7 ms; 4,348 KB
testcase_18	AC	7 ms; 4,348 KB
testcase_19	AC	64 ms; 4,348 KB
testcase_20	AC	4 ms; 4,348 KB
testcase_21	AC	157 ms; 4,348 KB
testcase_22	AC	2 ms; 4,348 KB
testcase_23	AC	2 ms; 4,348 KB
testcase_24	AC	2 ms; 4,348 KB
testcase_25	AC	2 ms; 4,348 KB
testcase_26	AC	2 ms; 4,348 KB
testcase_27	AC	2 ms; 4,348 KB
testcase_28	AC	8 ms; 4,348 KB
testcase_29	AC	79 ms; 4,348 KB
testcase_30	AC	2 ms; 4,348 KB
testcase_31	AC	15 ms; 4,348 KB
testcase_32	AC	2 ms; 4,348 KB
testcase_33	AC	110 ms; 4,348 KB
testcase_34	AC	61 ms; 4,348 KB
testcase_35	AC	3 ms; 4,348 KB
testcase_36	AC	3 ms; 4,348 KB
testcase_37	AC	2 ms; 4,348 KB
testcase_38	AC	4 ms; 4,348 KB
testcase_39	AC	2 ms; 4,348 KB
testcase_40	AC	2 ms; 4,348 KB
testcase_41	AC	2 ms; 4,348 KB
testcase_42	AC	2 ms; 4,348 KB
testcase_43	AC	19 ms; 4,348 KB
testcase_44	AC	11 ms; 4,348 KB
testcase_45	AC	353 ms; 4,348 KB
testcase_46	AC	13 ms; 4,348 KB
testcase_47	AC	91 ms; 4,348 KB
testcase_48	AC	84 ms; 4,348 KB
testcase_49	AC	10 ms; 4,348 KB
testcase_50	AC	2 ms; 4,348 KB
testcase_51	AC	2 ms; 4,348 KB
testcase_52	AC	20 ms; 4,348 KB
testcase_53	AC	10 ms; 4,348 KB
testcase_54	AC	119 ms; 4,348 KB
testcase_55	AC	119 ms; 4,348 KB
testcase_56	AC	119 ms; 4,348 KB
testcase_57	AC	231 ms; 4,348 KB
testcase_58	AC	231 ms; 4,348 KB
testcase_59	AC	231 ms; 4,348 KB

ソースコード

#line 1 "graph/test/shortest_cycle.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1320"

#line 2 "graph/shortest_cycle.hpp"

#include <algorithm>
#include <cassert>
#include <limits>
#include <optional>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

// Shortest cycle detection of graphs
// Verified: https://yukicoder.me/submissions/594507
template <bool DIRECTED, typename T> struct shortest_cycle {
    int V;
    std::vector<std::vector<std::tuple<int, int, T>>> to; // (nxt, edge_idx, weight)
    std::vector<std::tuple<int, int, T>> edges;

    shortest_cycle(int V = 0) : V(V), to(V) {}

    void add_edge(int s, int t, T weight) {
        static_assert(DIRECTED);
        assert(0 <= s and s < V);
        assert(0 <= t and t < V);
        assert(weight >= 0);
        to.at(s).emplace_back(t, (int)edges.size(), weight);
        edges.emplace_back(s, t, weight);
    }

    void add_bi_edge(int s, int t, T weight) {
        static_assert(!DIRECTED);
        assert(0 <= s and s < V);
        assert(0 <= t and t < V);
        assert(weight >= 0);
        to.at(s).emplace_back(t, (int)edges.size(), weight);
        to.at(t).emplace_back(s, (int)edges.size(), weight);
        edges.emplace_back(s, t, weight);
    }

    std::vector<T> dist;
    std::vector<int> prv;

    std::pair<T, std::pair<int, int>> Solve(const int &v) {
        assert(0 <= v and v < V);
        dist.assign(V, T());
        prv.assign(V, -1);
        std::vector<int> prve(V, -1);
        std::vector<int> orig(V, -1);

        auto reached = [&](int i) { return i == v or prv.at(i) != -1; };

        std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<>> pq;
        pq.emplace(dist.at(v), v);

        while (!pq.empty()) {
            const auto [d_, now] = pq.top();
            pq.pop();
            if (d_ > dist.at(now)) continue;

            for (const auto &[nxt, eid, w] : to[now]) {
                if (reached(nxt) and dist.at(nxt) <= dist.at(now) + w) continue;
                dist.at(nxt) = dist.at(now) + w;
                orig.at(nxt) = orig.at(now) < 0 ? nxt : orig.at(now);
                prv.at(nxt) = now;
                prve.at(nxt) = eid;
                pq.emplace(dist.at(nxt), nxt);
            }
        }

        std::vector<bool> is_edge_used(edges.size());
        for (int eid : prve) {
            if (eid >= 0) is_edge_used.at(eid) = true;
        }

        std::optional<T> minimum_cycle = std::nullopt;
        int s = -1, t = -1;

        for (int eid = 0; eid < (int)edges.size(); ++eid) {
            if (is_edge_used.at(eid)) continue;
            auto [a, b, w] = edges.at(eid);
            if (!reached(a) or !reached(b)) continue;

            if constexpr (DIRECTED) {
                if (b != v) continue;
            } else {
                if (orig.at(a) == orig.at(b) and (a != v or b != v)) continue;
            }

            if (T L = dist.at(a) + dist.at(b) + w;
                !minimum_cycle.has_value() or L < minimum_cycle.value()) {
                minimum_cycle = L;
                s = a, t = b;
            }
        }

        return std::make_pair(minimum_cycle.value_or(T(-1)), std::make_pair(s, t));
    }

    std::vector<int> retrieve_loop(const std::pair<int, int> &ab) const {
        if (ab.first < 0 or ab.second < 0) return {};
        std::vector<int> ret;
        bool initial = true;
        for (int cur : {ab.first, ab.second}) {
            while (cur >= 0) {
                ret.push_back(cur);
                cur = prv.at(cur);
            }
            if (initial) {
                std::reverse(ret.begin(), ret.end());
                initial = false;
            } else {
                ret.pop_back();
            }
        }
        return ret;
    }
};
#line 4 "graph/test/shortest_cycle.test.cpp"

#include <iostream>
#line 7 "graph/test/shortest_cycle.test.cpp"
using namespace std;

int main() {
    int T, N, M;
    cin >> T >> N >> M;
    const long long INF = 1LL << 60;
    long long ret = INF;

    if (T == 1) {
        // Directed graph
        shortest_cycle<true, long long> graph(N);
        while (M--) {
            int u, v, w;
            cin >> u >> v >> w;
            u--, v--;
            graph.add_edge(u, v, w);
        }
        for (int s = 0; s < N; s++) {
            auto len = graph.Solve(s).first;
            if (len >= 0) ret = min(ret, len);
        }
    } else {
        // Undirected graph
        shortest_cycle<false, long long> graph(N);
        while (M--) {
            int u, v, w;
            cin >> u >> v >> w;
            u--, v--;
            graph.add_bi_edge(u, v, w);
        }
        for (int i = 0; i < N; i++) {
            auto len = graph.Solve(i).first;
            if (len >= 0) ret = min(ret, len);
        }
    }
    cout << (ret < INF ? ret : -1) << '\n';
}