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

• 問題: No.1320 Two Type Min Cost Cycle
• ユーザー: umimel
• 提出日時: 2024-03-01 04:40:34
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,028 ms / 2,000 ms
• コード長: 7,430 bytes
• コンパイル時間: 7,776 ms
• コンパイル使用メモリ: 189,168 KB
• 実行使用メモリ: 6,676 KB
• 最終ジャッジ日時: 2024-03-01 04:40:58
• 合計ジャッジ時間: 12,243 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,676 KB
testcase_01	AC	2 ms; 6,676 KB
testcase_02	AC	3 ms; 6,676 KB
testcase_03	AC	2 ms; 6,676 KB
testcase_04	AC	2 ms; 6,676 KB
testcase_05	AC	4 ms; 6,676 KB
testcase_06	AC	3 ms; 6,676 KB
testcase_07	AC	13 ms; 6,676 KB
testcase_08	AC	53 ms; 6,676 KB
testcase_09	AC	665 ms; 6,676 KB
testcase_10	AC	15 ms; 6,676 KB
testcase_11	AC	512 ms; 6,676 KB
testcase_12	AC	126 ms; 6,676 KB
testcase_13	AC	282 ms; 6,676 KB
testcase_14	AC	33 ms; 6,676 KB
testcase_15	AC	16 ms; 6,676 KB
testcase_16	AC	3 ms; 6,676 KB
testcase_17	AC	7 ms; 6,676 KB
testcase_18	AC	8 ms; 6,676 KB
testcase_19	AC	56 ms; 6,676 KB
testcase_20	AC	11 ms; 6,676 KB
testcase_21	AC	332 ms; 6,676 KB
testcase_22	AC	2 ms; 6,676 KB
testcase_23	AC	2 ms; 6,676 KB
testcase_24	AC	2 ms; 6,676 KB
testcase_25	AC	2 ms; 6,676 KB
testcase_26	AC	2 ms; 6,676 KB
testcase_27	AC	2 ms; 6,676 KB
testcase_28	AC	29 ms; 6,676 KB
testcase_29	AC	83 ms; 6,676 KB
testcase_30	AC	2 ms; 6,676 KB
testcase_31	AC	15 ms; 6,676 KB
testcase_32	AC	2 ms; 6,676 KB
testcase_33	AC	492 ms; 6,676 KB
testcase_34	AC	234 ms; 6,676 KB
testcase_35	AC	2 ms; 6,676 KB
testcase_36	AC	3 ms; 6,676 KB
testcase_37	AC	2 ms; 6,676 KB
testcase_38	AC	3 ms; 6,676 KB
testcase_39	AC	2 ms; 6,676 KB
testcase_40	AC	2 ms; 6,676 KB
testcase_41	AC	2 ms; 6,676 KB
testcase_42	AC	2 ms; 6,676 KB
testcase_43	AC	16 ms; 6,676 KB
testcase_44	AC	9 ms; 6,676 KB
testcase_45	AC	1,028 ms; 6,676 KB
testcase_46	AC	12 ms; 6,676 KB
testcase_47	AC	402 ms; 6,676 KB
testcase_48	AC	79 ms; 6,676 KB
testcase_49	AC	9 ms; 6,676 KB
testcase_50	AC	2 ms; 6,676 KB
testcase_51	AC	2 ms; 6,676 KB
testcase_52	AC	60 ms; 6,676 KB
testcase_53	AC	33 ms; 6,676 KB
testcase_54	AC	110 ms; 6,676 KB
testcase_55	AC	112 ms; 6,676 KB
testcase_56	AC	111 ms; 6,676 KB
testcase_57	AC	475 ms; 6,676 KB
testcase_58	AC	467 ms; 6,676 KB
testcase_59	AC	478 ms; 6,676 KB

コンパイルメッセージ

main.cpp: In member function 'std::vector<std::pair<_BiIter, int> > directed_min_weight_cycle<T>::dijkstra(int)':
main.cpp:66:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   66 |             auto [tmp, v] = pq.top();
      |                  ^
main.cpp: In member function 'std::vector<std::pair<_BiIter, int> > undirected_min_weight_cycle<T>::dijkstra(int)':
main.cpp:179:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  179 |             auto [tmp, v] = pq.top();
      |                  ^

ソースコード

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i)
#define rep(i, n) drep(i, 0, n - 1)
#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, to;
    T cost;
    int id;

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

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 weighted_graph = vector<Edges<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 directed_min_weight_cycle{
    int n;
    weighted_graph<T> G;
    const T TINF = numeric_limits<T>::max()/2;

    directed_min_weight_cycle(weighted_graph<T> G_) : G(G_){
        n = (int)G.size();
    }

    // return dist, dist[v] = {dist(r, v), parent of r};
    vector<pair<T, int>> dijkstra(int r){
        vector<pair<T, int>> dist(n, {TINF, -1});
        dist[r].first = 0;
        priority_queue<pair<T, int>, vector<pair<long long, int>>, greater<>> pq;
        pq.push({0, r});
        while(!pq.empty()){
            auto [tmp, v] = pq.top();
            pq.pop();
            if(dist[v].first < tmp) continue;

            for(edge<T> e : G[v]){
                if(dist[v].first+e.cost < dist[e.to].first){
                    dist[e.to].first = dist[v].first+e.cost;
                    dist[e.to].second = v;
                    pq.push({dist[e.to].first, e.to});
                }
            }
        }

        return dist;
    }

    /*
        # return weight of min weight cycle including vertex r
        # if there does not exist cycle, return -1
    */
    T get_weight(int r){
        vector<pair<T, int>> dist = dijkstra(r);
        T ans = TINF;
        for(int v=0; v<n; v++) for(edge<T> e : G[v]) if(e.to == r){
            ans = min(ans, dist[v].first + e.cost);
        }

        if(ans == TINF) return T(-1);
        else return ans;
    }

    /*
        # return weight of min weight cycle
        # if there does not exist cycle, return -1
    */
    T get_weight(){
        T ans = TINF;
        for(int r=0; r<n; r++){
            T sa = get_weight(r);
            if(sa != -1) ans = min(ans, sa);
        }

        if(ans == TINF) return T(-1);
        else return ans;
    }

    vector<int> get_cycle(int r){
        vector<pair<T, int>> dist = dijkstra(r);
        T weight = TINF;
        int last = -1;
        for(int v=0; v<n; v++) for(edge<T> e : G[v]) if(e.to == r){
            if(dist[v].first + e.cost < weight){
                weight = dist[v].first + e.cost;
                last = v;
            }
        }

        vector<int> ans;
        while(last != -1){
            ans.push_back(last);
            last = dist[last].second;
        }
        reverse(all(ans));

        return ans;
    }

    vector<int> get_cycle(){
        vector<int> ans;
        T weight = TINF;
        for(int r=0; r<n; r++){
            vector<pair<T, int>> dist = dijkstra(r);
            T sw = TINF;
            int last = -1;
            for(int v=0; v<n; v++) for(edge<T> e : G[v]) if(e.to == r){
                if(dist[v].first + e.cost < sw){
                    sw = dist[v].first + e.cost;
                    last = v;
                }
            }

            if(weight <= sw) continue;

            vector<int> ans;
            while(last != -1){
                ans.push_back(last);
                last = dist[last].second;
            }
        }

        reverse(all(ans));

        return ans;
    }
};

template<typename T>
struct undirected_min_weight_cycle{
    int n;
    weighted_graph<T> G;
    const T TINF = numeric_limits<T>::max()/2;

    undirected_min_weight_cycle(weighted_graph<T> G_) : G(G_){
        n = (int)G.size();
    }

    // return dist, dist[v] = {dist(r, v), parent of r};
    vector<pair<T, int>> dijkstra(int r){
        vector<pair<T, int>> dist(n, {TINF, -1});
        dist[r].first = 0;
        priority_queue<pair<T, int>, vector<pair<long long, int>>, greater<>> pq;
        pq.push({0, r});
        while(!pq.empty()){
            auto [tmp, v] = pq.top();
            pq.pop();
            if(dist[v].first < tmp) continue;

            for(edge<T> e : G[v]){
                if(dist[v].first+e.cost < dist[e.to].first){
                    dist[e.to].first = dist[v].first+e.cost;
                    dist[e.to].second = v;
                    pq.push({dist[e.to].first, e.to});
                }
            }
        }

        return dist;
    }

    /*
        # return weight of min weight cycle including vertex r
        # if there does not exist cycle, return -1
    */
    T get_weight(int r){
        vector<pair<T, int>> dist = dijkstra(r);
        tree<int> spt(n);
        for(int v=0; v<n; v++) if(v!=r && dist[v].first != TINF){
            spt[v].push_back(edge<int>(dist[v].second));
            spt[dist[v].second].push_back(edge<int>(v));
        }

        vector<int> label(n, -1);
        label[r] = r;
        function<void(int, int, int)> dfs = [&](int v, int p, int l){
            label[v] = l;
            for(edge<int> e : spt[v]) if(e.to != p) dfs(e.to, v, l);
        };

        for(edge<int> e : spt[r]){
            dfs(e.to, r, e.to);
        }

        T ans = TINF;
        for(int v=0; v<n; v++) if(v != r) for(edge<T> e : G[v]){
            if(dist[v].second != e.to && label[v] != label[e.to]){
                ans = min(ans, dist[v].first + dist[e.to].first + e.cost);
            }
        }

        if(ans == TINF) return T(-1);
        else return ans;
    }

    /*
        # return weight of min weight cycle
        # if there does not exist cycle, return -1
    */
    T get_weight(){
        T ans = TINF;
        for(int r=0; r<n; r++){
            T sa = get_weight(r);
            if(sa != -1) ans = min(ans, sa);
        }

        if(ans == TINF) return T(-1);
        else return ans;
    }
};

void solve(){
    int type, n, m; cin >> type >> n >> m;
    weighted_graph<ll> G(n);
    for(int i=0; i<m; i++){
        int u, v; cin >> u >> v;
        u--; v--;
        ll w; cin >> w;
        G[u].push_back(edge<ll>(v, w));
        if(type==0) G[v].push_back(edge<ll>(u, w));
    }

    if(type == 0){
        undirected_min_weight_cycle<ll> mwc(G);
        cout << mwc.get_weight() << '\n';
    }
    if(type == 1){
        directed_min_weight_cycle<ll> mwc(G);
        cout << mwc.get_weight() << '\n';
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int T=1;
    //cin >> T;
    while(T--) solve();
}