#1164286 (C++14) No.1320 Two Type Min Cost Cycle

• 問題: No.1320 Two Type Min Cost Cycle
• ユーザー: umimel
• 提出日時: 2026-05-11 04:51:33
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 865 ms / 2,000 ms
• コード長: 8,364 bytes
• コンパイル時間: 1,680 ms
• コンパイル使用メモリ: 212,508 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-05-11 04:51:49
• 合計ジャッジ時間: 14,141 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 57

コンパイルメッセージ

main.cpp: In member function 'void shortest_path_tree<T>::run()':
main.cpp:175:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  175 |             auto [d, v] = que.top();
      |                  ^

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define fi first
#define se second
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const ll MOD1000000007 = 1000000007;
const ll MOD998244353 = 998244353;
const ll MOD[3] = {999727999, 1070777777, 1000000007};
const ll LINF = 1LL << 60LL;
const int IINF = (1 << 30) - 1;


template<typename T> 
struct edge{
    int from = -1;
    int to = -1;
    T cost = T(1);
    int id = -1;

    edge() = default;
    edge(int to, T cost=T(1)) : to(to), cost(cost){}
    edge(int from, int to, T cost, int id=-1) : from(from), to(to), cost(cost), id(id){}

    void reverse(){swap(from, to);}
    edge rev() const { return edge(to, from, cost, id); }
};

template<typename T>
struct edges : std::vector<edge<T>>{
    using std::vector<edge<T>>::vector;

    void sort_by_cost(){
        std::sort(
            (*this).begin(),
            (*this).end(), 
            [](const edge<T>& a, const edge<T>& b){
                return a.cost < b.cost;
            }
        );
    }

    void rsort_by_cost(){
        std::sort(
            (*this).begin(),
            (*this).end(), 
            [](const edge<T>& a, const edge<T>& b){
                return a.cost > b.cost;
            }
        );
    }

    void sort(){
        sort_by_cost();
    }
};

template<typename T = bool>
struct graph{
private:
    int n = 0;
    int m = 0;
    vector<edges<T>> adj;
    edges<T> es;
    bool dir = false;

public:
    graph() = default;
    graph(int n, bool dir=false) : n(n), adj(n), dir(dir){}

    int add_vertex(){
        adj.push_back(edges<T>());
        return n++;
    }

    int add_edge(int from, int to, T cost=T(1)){
        int id = m++;
        es.push_back(edge<T>(from, to, cost, id));
        if(dir){
            adj[from].push_back(edge<T>(from, to, cost, id));
        }else{
            adj[from].push_back(edge<T>(from, to, cost, id));
            adj[to].push_back(edge<T>(to, from, cost, id));
        }
        return id;
    }

    int size() const{
        return n;
    }

    bool empty() const{
        return n == 0;
    }

    edges<T>& operator[](int v){
        return adj[v];
    }

    const edges<T>& operator[](int v) const{
        return adj[v];
    }

    auto begin(){ return adj.begin(); }
    auto end(){ return adj.end(); }
    auto begin() const{ return adj.begin(); }
    auto end() const{ return adj.end(); }

    int edge_size() const{
        return m;
    }

    bool get_dir() const{
        return dir;
    }

    edge<T> get_edge(int i) const{
        return es[i];
    }

    const edges<T>& get_edge_set() const{
        return es;
    }

    const edges<T>& get_edges() const{
        return es;
    }
};

template<typename T>
struct redge{
    int from, to;
    T cap, cost;
    int rev;
    
    redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){}
    redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){}
};

template<typename T> using Edges = vector<edge<T>>;
template<typename T> using tree = vector<Edges<T>>;
using unweighted_graph = vector<vector<int>>;
template<typename T> using residual_graph = vector<vector<redge<T>>>;


template<typename T>
struct shortest_path_tree{
private:
    const T TINF = numeric_limits<T>::max()/3;
    int n, s;
    graph<T> G;
    vector<T> dist;
    vector<int> vpar;
    edges<T> epar;

public:
    shortest_path_tree(graph<T> G, int s) : G(G), s(s){
        n = G.size();
        dist.resize(n, TINF);
        vpar.resize(n, -1);
        epar.resize(n);
        run();
    }

    void run(){
        dist[s] = 0;
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> que;
        que.push({0, s});
        while(!que.empty()){
            auto [d, v] = que.top();
            que.pop();
            if(dist[v] < d) continue;

            for(auto e : G[v]){
                if(dist[v] + e.cost < dist[e.to]){
                    dist[e.to] = dist[v] + e.cost;
                    vpar[e.to] = v;
                    epar[e.to] = e;
                    que.push({dist[e.to], e.to});
                }
            }
        }
    }

    T get_dist(int t){
        return dist[t];
    }

    vector<T> get_dist(){
        return dist;
    }

    vector<int> get_vpar(){
        return vpar;
    }

    int get_vpar(int v){
        return vpar[v];
    }

    edges<T> get_epar(){
        return epar;
    }

    edge<T> get_epar(int v){
        return epar[v];
    }

    vector<int> get_vpath(int t){
        vector<int> vpath;
        int cur = t;
        while(cur != -1){
            vpath.push_back(cur);
            cur = vpar[cur];
        }
        reverse(vpath.begin(), vpath.end());
        return vpath;
    }

    edges<T> get_epath(int t){
        edges<T> epath;
        int cur = t;
        while(cur != s){
            epath.push_back(epar[cur]);
            cur = vpar[cur];
        }
        reverse(epath.begin(), epath.end());
        return epath;
    }

    graph<T> get_tree(){
        graph<T> spt(n, false);
        for(int v=0; v<n; v++) if(v != s){
            int p = vpar[v];
            if(p == -1) continue;
            auto e = epar[v];
            spt.add_edge(p, v, e.cost);
        }
        return spt;
    }

    graph<T> get_shotest_path_tree(){
        return get_tree();
    }
};


template<typename S>
edges<S> min_weight_cycle(graph<S> &G, int s){
    int n = G.size();
    const S SINF = numeric_limits<S>::max()/3;
    bool dir = G.get_dir();
    shortest_path_tree<S> dijk(G, s);
    auto dist = dijk.get_dist();
    edges<S> cyc;

    if(dir){
        S cost = SINF;
        edge<S> emin; 
        for(int v=0; v<n; v++) for(auto e : G[v]) if(e.to == s){
            if(dist[v] + e.cost < cost){
                cost = dist[v] + e.cost;
                emin = e;
            }
        }

        if(cost == SINF) return {};
        cyc = dijk.get_epath(emin.from);
        cyc.push_back(emin);
    }

    if(!dir){
        vector<vector<int>> ch(n);
        for(int v=0; v<n; v++) if(v != s && dijk.get_vpar(v)!=-1){
            ch[dijk.get_vpar(v)].push_back(v);
        }
        
        vector<int> label(n, -1);
        label[s] = s;
        function<void(int, int)> labeling = [&](int v, int l){
            label[v] = l;
            for(int to : ch[v]) labeling(to, l);
        };
        for(int to : ch[s]) labeling(to, to);

        S cost = SINF;
        edge<S> emin;
        for(int v=0; v<n; v++) if(v != s) for(auto e : G[v]){
            if(e.id != dijk.get_epar(v).id && label[v] != label[e.to] && dist[v] + dist[e.to] + e.cost < cost){
                cost = dist[v] + dist[e.to] + e.cost;
                emin = e;
            }   
        }

        if(cost == SINF) return {};

        cyc = dijk.get_epath(emin.from);
        cyc.push_back(emin);
        auto epath = dijk.get_epath(emin.to);
        reverse(epath.begin(), epath.end());
        for(auto e : epath){
            e.reverse();
            cyc.push_back(e);
        }
    }

    return cyc;
}

template<typename S>
edges<S> min_weight_cycle(graph<S> &G){
    int n = G.size();
    const S SINF = numeric_limits<S>::max()/2;
    S cost = SINF;
    edges<S> min_cyc;
    
    for(int s=0; s<n; s++){
        auto cyc = min_weight_cycle(G, s);
        if(cyc.empty()) continue;
        S sum = 0;
        for(auto e : cyc) sum += e.cost;
        if(sum < cost){
            cost = sum;
            min_cyc = cyc;
        }
    }

    return min_cyc;
}


int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int T; cin >> T;
    int n, m; cin >> n >> m;
    edges<ll> cyc;
    if(T == 0){
        graph<ll> G(n, false);
        for(int i=0; i<m; ++i){
            int u, v, w; cin >> u >> v >> w;
            G.add_edge(u-1, v-1, w);
        }
        cyc = min_weight_cycle(G);
    }

    if(T == 1){
        graph<ll> G(n, true);
        for(int i=0; i<m; ++i){
            int u, v, w; cin >> u >> v >> w;
            G.add_edge(u-1, v-1, w);
        }
        cyc = min_weight_cycle(G);
    }

    if(cyc.empty()){
        cout << -1 << '\n';
        return 0;
    }

    ll ans = 0LL;
    for(auto e : cyc) ans += e.cost;
    cout << ans << '\n';

    return 0;
}