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

提出ソース
結果

問題	No.1320 Two Type Min Cost Cycle
ユーザー	tonegawa
提出日時	2024-12-14 07:55:09
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	580 ms / 2,000 ms
コード長	16,240 bytes
コンパイル時間	3,389 ms
コンパイル使用メモリ	214,428 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-12-14 07:55:19
合計ジャッジ時間	9,383 ms
ジャッジサーバーID （参考情報）	judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 57
権限があれば一括ダウンロードができます
ソースコード

raw source code

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator << (std::ostream &dest, const std::pair<F, S> &p) {
    dest << p.first << ' ' << p.second;
    return dest;
}

template<typename A, typename B>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t);
    return dest;
}

template<typename A, typename B, typename C>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t);
    return dest;
}

template<typename A, typename B, typename C, typename D>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C, D> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t);
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<std::vector<T>> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz; i++) {
        int m = v[i].size();
        for (int j = 0; j < m; j++) dest << v[i][j] << (i != sz - 1 && j == m - 1 ? '\n' : ' ');
    }
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<T> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T, size_t sz>
std::ostream &operator << (std::ostream &dest, const std::array<T, sz> &v) {
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::set<T> &v) {
    for (auto itr = v.begin(); itr != v.end();) {
        dest << *itr;
        itr++;
        if (itr != v.end()) dest << ' ';
    }
    return dest;
}

template<typename T, typename E>
std::ostream &operator << (std::ostream &dest, const std::map<T, E> &v) {
    for (auto itr = v.begin(); itr != v.end(); ) {
        dest << '(' << itr->first << ", " << itr->second << ')';
        itr++;
        if (itr != v.end()) dest << '\n';
    }
    return dest;
}

template<typename T>
std::vector<T> make_vec(size_t sz, T val) { return std::vector<T>(sz, val); }

template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail) {
    return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}

template<typename T>
std::vector<T> read_vec(size_t sz) {
    std::vector<T> v(sz);
    for (int i = 0; i < (int)sz; i++) std::cin >> v[i];
    return v;
}

template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail) {
    auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
    for (int i = 0; i < (int)sz; i++) v[i] = read_vec<T>(tail...);
    return v;
}

template<typename T, size_t size>
auto make_array(T x) { 
    std::array<T, size> res;
    res.fill(x);
    return res;
}

template<typename T, size_t size, size_t size2, size_t... Tail>
auto make_array(T x) {
    std::array<decltype(make_array<T, size2, Tail...>(x)), size> res;
    res.fill(make_array<T, size2, Tail...>(x));
    return res;
}


// x / y以上の最小の整数
ll ceil_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? y - 1 : 0)) / y;
}

// x / y以下の最大の整数
ll floor_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? 0 : -y + 1)) / y;
}

void io_init() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
}






template<typename _W>
struct edge_base {
    using W = _W;
    int t;
    edge_base() {}
    edge_base(int _t) : t(_t) {}

    virtual int from() const {
        assert(false);
    }

    int to() const {
        return t;
    }
    
    virtual W weight() const {
        assert(false);
    }

    virtual int id() const {
        assert(false);
    }

    operator int() const {
        return t;
    }
};

struct simple_edge : edge_base<int> {
    simple_edge() {}
    simple_edge(int _t) : edge_base<int>(_t) {}
    int weight() const override {
        return 1;
    }
    int id() const override {
        return -1;
    }
};

struct labeled_edge : edge_base<int> {
    int _s, _id;
    labeled_edge() {}
    labeled_edge(int _s, int _t, int _id) : edge_base<int>(_t), _s(_s), _id(_id) {}
    int weight() const override {
        return 1;
    }
    int from() const override {
        return _s;
    }
    int id() const override {
        return _id;
    }
};

template<typename _W>
struct weighted_edge : edge_base<_W> {
    using W = _W;
    W w;
    weighted_edge() {}
    weighted_edge(int _t, _W _w) : edge_base<_W>(_t), w(_w) {}
    W weight() const override {
        return w;
    }
    int id() const override {
        return -1;
    }
};

template<typename _W>
struct weighted_labeled_edge : edge_base<_W> {
    using W = _W;
    W w;
    int _s, _id;
    weighted_labeled_edge() : _id(-1) {}
    weighted_labeled_edge(int _s, int _t, _W _w, int _id) : edge_base<_W>(_t), w(_w), _s(_s), _id(_id) {}
    int from() const override {
        return _s;
    }
    W weight() const override {
        return w;
    }
    int id() const override {
        return _id;
    }
};





template <class E>
struct csr {
    std::vector<int> start;
    std::vector<E> elist;
    csr() {}
    explicit csr(int n, const std::vector<std::pair<int, E>>& edges) : start(n + 1), elist(edges.size()) {
        for (auto e : edges) {
            start[e.first + 1]++;
        }
        for (int i = 1; i <= n; i++) {
            start[i] += start[i - 1];
        }
        auto counter = start;
        for (auto e : edges) {
            elist[counter[e.first]++] = e.second;
        }
    }
    ~csr() {}

    int N() const {
        return start.size() - 1;
    }

    int deg(int i) const {
        return start[i + 1] - start[i];
    }

    int begin(int i) const {
        return start[i];
    }

    int end(int i) const {
        return start[i + 1];
    }

    E& operator [] (int i) { return elist[i]; }
};


// 全体の最小コスト閉路
// 重みあり  O(V(V + E)logV)
template<typename edge>
struct cycle_detection_mincost {
    using W = typename edge::W;
    static constexpr W inf = std::numeric_limits<W>::max() / 2;
  private:
    csr<edge> g;

    std::pair<std::vector<W>, std::vector<edge>> bfs_tree(int s) {
        int N = g.N();
        std::vector<W> dist(N, inf);
        std::vector<edge> par(N);
        std::queue<int> q;
        q.push(s);
        dist[s] = 0;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int i = g.begin(v); i < g.end(v); i++) {
                int to = g[i];
                if (dist[v] + 1 < dist[to]) {
                    dist[to] = dist[v] + 1;
                    par[to] = g[i];
                    q.push(to);
                }
            }
        }
        return {dist, par};
    }
    
    std::pair<std::vector<W>, std::vector<edge>> dijkstra_tree(int s) {
        int N = g.N();
        std::vector<W> dist(N, inf);
        std::vector<edge> par(N);
        using P = std::pair<W, int>;
        std::priority_queue<P, std::vector<P>, std::greater<P>> q;
        q.push({0, s});
        dist[s] = 0;
        while (!q.empty()) {
            auto [d, v] = q.top();
            q.pop();
            if (dist[v] != d) continue;
            for (int i = g.begin(v); i < g.end(v); i++) {
                int to = g[i];
                W nd = dist[v] + g[i].weight();
                if (nd < dist[to]) {
                    dist[to] = nd;
                    par[to] = g[i];
                    q.push({nd, to});
                }
            }
        }
        return {dist, par};
    }

  public:
    cycle_detection_mincost(const csr<edge> &_g) : g(_g) {}

    // vを含む最小閉路
    // 無向グラフの場合のみ辺のs-tが逆になっている場合があるがidの順序は正しい
    // 重みあり O((V + E)logV)
    // 重みなし O(V + E)
    std::pair<W, std::vector<edge>> find(int v, bool directed, bool weighted, bool accept_self_loop) {
        int N = g.N();
        W w = inf;
        int eid = -1;
        if (accept_self_loop) {
            for (int j = g.begin(v); j < g.end(v); j++) {
                if (g[j].to() == v && w < g[j].weight()) {
                    w = g[j].weight();
                    eid = j;
                }
            }
        }
        std::vector<W> dist;
        std::vector<edge> par;
        std::vector<int> semi_root;

        if (weighted) {
            std::tie(dist, par) = dijkstra_tree(v);
        } else {
            std::tie(dist, par) = bfs_tree(v);
        }
        if (directed) {
            for (int i = 0; i < N; i++) {
                if (i == v || dist[i] == inf || dist[i] > w) continue;
                for (int j = g.begin(i); j < g.end(i); j++) {
                    if (g[j].to() == v && dist[i] + g[j].weight() < w) {
                        w = dist[i] + g[j].weight();
                        eid = j;
                    }
                }
            }
        } else {
            semi_root.resize(N, -1);
            auto dfs = [&](auto &&dfs, int u, int p, int sr) -> void {
                semi_root[u] = sr;
                for (int i = g.begin(u); i < g.end(u); i++) {
                    int to = g[i];
                    if (to == v || to == p || to == u || dist[to] == inf) continue;
                    if (par[to].id() == g[i].id()) {
                        dfs(dfs, to, u, sr);
                    }
                }
            };
            for (int i = 0; i < N; i++) {
                if (i == v || dist[i] == inf) continue;
                if (par[i].from() == v) dfs(dfs, i, v, i);
            }
            for (int i = 0; i < N; i++) {
                if (i == v || dist[i] == inf || dist[i] > w) continue;
                for (int j = g.begin(i); j < g.end(i); j++) {
                    int to = g[j];
                    if (g[j].id() == par[i].id()) continue;
                    if (semi_root[i] == semi_root[to]) continue;
                    if (dist[i] + dist[to] + g[j].weight() < w) {
                        w = dist[i] + dist[to] + g[j].weight();
                        eid = j;
                    }
                }
            }
        }
        if (w == inf) return {inf, {}};
        std::vector<edge> res;
        res.push_back(g[eid]);
        int u = g[eid].from();
        while (u != v) {
            res.push_back(par[u]);
            u = par[u].from();
        }
        std::reverse(res.begin(), res.end());
        if (!directed) {
            u = g[eid].to();
            while (u != v) {
                res.push_back(par[u]);
                u = par[u].from();
            }
        }
        return {w, res};
    }

    // 最小閉路
    // 無向グラフの場合のみ辺のs-tが逆になっている場合があるがidの順序は正しい
    // 重みあり O((V + E)logV)
    // 重みなし O(V + E)
    std::pair<W, std::vector<edge>> find(bool directed, bool weighted, bool accept_self_loop) {
        int N = g.N();
        W w = inf;
        int r = -1, eid = -1;
        if (accept_self_loop) {
            for (int v = 0; v < N; v++) {
                for (int j = g.begin(v); j < g.end(v); j++) {
                    if (g[j].to() == v && w < g[j].weight()) {
                        w = g[j].weight();
                        r = v;
                        eid = j;
                    }
                }
            }
        }
        std::vector<W> dist;
        std::vector<edge> par;
        std::vector<int> semi_root(N, -1);
        std::vector<int> ord(N);
        std::iota(ord.begin(), ord.end(), 0);
        std::random_device seed_gen;
        std::mt19937 engine(seed_gen());
        std::shuffle(ord.begin(), ord.end(), engine);

        for (int v : ord) {
            if (weighted) {
                std::tie(dist, par) = dijkstra_tree(v);
            } else {
                std::tie(dist, par) = bfs_tree(v);
            }
            if (directed) {
                for (int i = 0; i < N; i++) {
                    if (i == v || dist[i] == inf || dist[i] > w) continue;
                    for (int j = g.begin(i); j < g.end(i); j++) {
                        if (g[j].to() == v && dist[i] + g[j].weight() < w) {
                            w = dist[i] + g[j].weight();
                            eid = j;
                            r = v;
                        }
                    }
                }
            } else {
                std::fill(semi_root.begin(), semi_root.end(), -1);
                auto dfs = [&](auto &&dfs, int u, int p, int sr) -> void {
                    semi_root[u] = sr;
                    for (int i = g.begin(u); i < g.end(u); i++) {
                        int to = g[i];
                        if (to == v || to == p || to == u || dist[to] == inf) continue;
                        if (par[to].id() == g[i].id()) {
                            dfs(dfs, to, u, sr);
                        }
                    }
                };
                for (int i = 0; i < N; i++) {
                    if (i == v || dist[i] == inf) continue;
                    if (par[i].from() == v) dfs(dfs, i, v, i);
                }
                for (int i = 0; i < N; i++) {
                    if (i == v || dist[i] == inf || dist[i] > w) continue;
                    for (int j = g.begin(i); j < g.end(i); j++) {
                        int to = g[j];
                        if (g[j].id() == par[i].id()) continue;
                        if (semi_root[i] == semi_root[to]) continue;
                        if (dist[i] + dist[to] + g[j].weight() < w) {
                            w = dist[i] + dist[to] + g[j].weight();
                            r = v;
                            eid = j;
                        }
                    }
                }
            }
        }        
        if (w == inf) return {inf, {}};
        if (weighted) {
            std::tie(dist, par) = dijkstra_tree(r);
        } else {
            std::tie(dist, par) = bfs_tree(r);
        }
        std::vector<edge> res;
        res.push_back(g[eid]);
        int u = g[eid].from();
        while (u != r) {
            res.push_back(par[u]);
            u = par[u].from();
        }
        std::reverse(res.begin(), res.end());
        if (!directed) {
            u = g[eid].to();
            while (u != r) {
                res.push_back(par[u]);
                u = par[u].from();
            }
        }
        return {w, res};
    }
};


int main() {
    io_init();
    int T;
    std::cin >> T;
    int N, M;
    std::cin >> N >> M;
    using edge = weighted_labeled_edge<long long>;
    std::vector<std::pair<int, edge>> E;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        std::cin >> a >> b >> c;
        a--, b--;
        E.push_back({a, {a, b, c, i}});
        if (T == 0) {
            E.push_back({b, {b, a, c, i}});
        }
    }
    cycle_detection_mincost<edge> G(csr<edge>(N, E));
    long long w = G.find(T, true, true).first;
    std::cout << (w == G.inf ? -1 : w) << '\n';
}
yukicoder

結果

ソースコード
