結果

問題 No.1320 Two Type Min Cost Cycle
コンテスト
ユーザー umimel
提出日時 2024-03-01 04:40:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 993 ms / 2,000 ms
コード長 7,430 bytes
コンパイル時間 2,185 ms
コンパイル使用メモリ 187,992 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-09-29 13:06:28
合計ジャッジ時間 10,205 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます
コンパイルメッセージ
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();
      |                  ^

ソースコード

diff # 

#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();
}
0