#981740 (C++17) No.1320 Two Type Min Cost Cycle

提出ソース

結果

問題	No.1320 Two Type Min Cost Cycle
ユーザー	K U
提出日時	2024-05-16 20:51:20
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	362 ms / 2,000 ms
コード長	6,620 bytes
コンパイル時間	2,571 ms
コンパイル使用メモリ	231,380 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-05-16 20:51:28
合計ジャッジ時間	7,410 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,948 KB
testcase_06	AC	3 ms 6,940 KB
testcase_07	AC	15 ms 6,944 KB
testcase_08	AC	22 ms 6,940 KB
testcase_09	AC	291 ms 6,940 KB
testcase_10	AC	20 ms 6,940 KB
testcase_11	AC	192 ms 6,944 KB
testcase_12	AC	42 ms 6,944 KB
testcase_13	AC	104 ms 6,940 KB
testcase_14	AC	17 ms 6,940 KB
testcase_15	AC	20 ms 6,940 KB
testcase_16	AC	3 ms 6,944 KB
testcase_17	AC	8 ms 6,944 KB
testcase_18	AC	8 ms 6,948 KB
testcase_19	AC	55 ms 6,944 KB
testcase_20	AC	6 ms 6,940 KB
testcase_21	AC	189 ms 6,944 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	1 ms 6,940 KB
testcase_24	AC	2 ms 6,948 KB
testcase_25	AC	2 ms 6,944 KB
testcase_26	AC	2 ms 6,944 KB
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	16 ms 6,940 KB
testcase_29	AC	109 ms 6,944 KB
testcase_30	AC	2 ms 6,944 KB
testcase_31	AC	19 ms 6,940 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	134 ms 6,940 KB
testcase_34	AC	74 ms 6,940 KB
testcase_35	AC	2 ms 6,940 KB
testcase_36	AC	2 ms 6,940 KB
testcase_37	AC	2 ms 6,940 KB
testcase_38	AC	3 ms 6,940 KB
testcase_39	AC	2 ms 6,944 KB
testcase_40	AC	2 ms 6,940 KB
testcase_41	AC	2 ms 6,944 KB
testcase_42	AC	2 ms 6,940 KB
testcase_43	AC	23 ms 6,944 KB
testcase_44	AC	10 ms 6,944 KB
testcase_45	AC	362 ms 6,940 KB
testcase_46	AC	14 ms 6,940 KB
testcase_47	AC	96 ms 6,944 KB
testcase_48	AC	95 ms 6,944 KB
testcase_49	AC	11 ms 6,940 KB
testcase_50	AC	1 ms 6,940 KB
testcase_51	AC	2 ms 6,944 KB
testcase_52	AC	19 ms 6,940 KB
testcase_53	AC	10 ms 6,944 KB
testcase_54	AC	106 ms 6,944 KB
testcase_55	AC	109 ms 6,944 KB
testcase_56	AC	104 ms 6,944 KB
testcase_57	AC	221 ms 6,940 KB
testcase_58	AC	223 ms 6,944 KB
testcase_59	AC	229 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// #pragma GCC target("avx512f")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops") // ループの部分展開

#include <bits/stdc++.h>
// #include <atcoder/all>
// using namespace atcoder;
#ifdef LOCAL
#include <debug.h>
#define dbg(...) debug::dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...) void(0)
#endif
using namespace std;

// #define int ll

#define rep(i, a, b) for(auto i=static_cast<signed>(a), i##_end__=static_cast<signed>(b); i < i##_end__; i++)
#define rep_r(i, a, b) for(auto i=static_cast<signed>(a), i##_end__=static_cast<signed>(b); i >= i##_end__; i--)
#define fore(i, a) for(auto& i: a)
#define forei(i, it, a) for(auto [i, it] = std::pair{0, std::begin(a)}; it != std::end(a); i++, it++)
#define all(x) std::begin(x), std::end(x)

using ll = long long; // __int128;
using ull = unsigned long long;
template<class T> using priority_queue_asc = priority_queue<T, vector<T>, greater<T>>;

template<class T> ostream& operator<<(ostream& os, const vector<T>& v){ rep(i, 0, v.size()){ os << (i == 0 ? "" : " ") << v[i]; } return os; }
template<class T, class S> istream& operator>>(istream& is, pair<T, S>& p) { is >> p.first >> p.second; return is; }
template<class T> istream& operator>>(istream& is, vector<T>& v) { fore(e, v){ is >> e; } return is; }

template<class C> int siz(const C& c) { return static_cast<int>(c.size()); }
template<class T, size_t N> constexpr int siz(const T (&)[N]) { return static_cast<int>(N); }
template<class A, class V> constexpr void fil(A& a, const V &v){ if constexpr(is_array_v<A>) for(auto& s: a) fil(s, v); else a = v; };
template<class V> constexpr auto vct(size_t n, const V& v){ return vector(n, v); } template <class... A> constexpr auto vct(size_t n, A... a){ return vector(n, vct(a...)); }
template<class T, class S> constexpr bool chmax(T& a, S b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> constexpr bool chmin(T& a, S b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> constexpr T pow2(T x){ return x * x; }
template<class T, class S> constexpr T divceil(T x, S div) { return (x % div == 0) ? x / div : (x >= 0) ? (x / div) + 1 : -((-x) / div); }
template<class T, class S> constexpr T divfloor(T x, S div){ return (x % div == 0) ? x / div : (x >= 0) ? (x / div) : -((-x) / div) - 1; }
template<class T, class S> inline void outif(bool c, T t, S f){ if(c) cout << t << endl; else cout << f << endl; }
inline void yesno(bool x){ cout << (x ? "Yes" : "No") << endl; }
constexpr long long INF = 1LL << 60; // 1.15e18
constexpr int MOD = (int)1e9 + 7;

// 最短路木 - ヒープバージョン O((N+M)logN)
// 戻り値: d[v]=最短距離(重み), p[v]=親頂点(rootの場合、-1), l[v]=通る経路の色分け。最初の頂点(root直下の頂点番号) 
template<class T> tuple<vector<T>, vector<int>, vector<int>> shortest_path_tree(const vector<vector<pair<int, T>>>& g, int root, T inf = numeric_limits<T>::max()){
    const int n = siz(g);
    vector<T> d(n, inf);
    vector<int> p(n, -1), l(n, -1);
    vector<bool> done(n);
    priority_queue_asc<pair<T, int>> q;
    d[root] = 0;
    q.push({d[root], root});
    while(!q.empty()){
        auto [mn, v] = q.top(); q.pop();
        if(done[v]) continue;
        done[v] = true;
        for(auto [e, w] : g[v]){
            if(done[e]) continue;
            if(d[e] <= mn + w) continue;
            d[e] = mn + w;
            p[e] = v;
            l[e] = v == root ? e : l[v];
            q.push({d[e], e});
        }
    }
    return {d, p, l};
}

// 無向グラフ 最小サイクル - ヒープバージョン O((N+M)logN)
template<class T> pair<T, vector<int>> shortest_cycle_undirected(const vector<vector<pair<int, T>>>& g, int root, T inf = numeric_limits<T>::max()){
    const int n = siz(g);

    auto [d, p, l] = shortest_path_tree(g, root, inf);

    T mn = inf;
    int mu = -1, mv = -1;
    rep(u, 0, n) for(auto [v, w] : g[u]){
        if(u == root || v == root || l[u] == l[v] || d[u] >= inf || d[v] >= inf || w >= inf) continue;
        if(mn <= d[u] + d[v] + w) continue;
        mn = d[u] + d[v] + w;
        mu = u, mv = v;
    }
    if(mn == inf) return {inf, {}};
    vector<int> path;
    path.push_back(root);

    stack<int> st;
    int v = mu;
    while(v != root) st.push(v), v = p[v];
    while(!st.empty()) path.push_back(st.top()), st.pop();

    v = mv;
    while(v != root) path.push_back(v), v = p[v];

    return {mn, path};
}
template<class T> pair<T, vector<int>> shortest_cycle_undirected_all(const vector<vector<pair<int, T>>>& g, T inf = numeric_limits<T>::max()){
    T mn = inf;
    vector<int> path;
    rep(i, 0, siz(g)){
        auto [m, p] = shortest_cycle_undirected(g, i, inf);
        if(mn > m) mn = m, path = p;
    }
    return {mn, path};
}

// 有向グラフ 最小サイクル - ヒープバージョン O((N+M)logN)
template<class T> pair<T, vector<int>> shortest_cycle_directed(const vector<vector<pair<int, T>>>& g, int root, T inf = numeric_limits<T>::max()){
    const int n = siz(g);

    auto [d, p, l] = shortest_path_tree(g, root, inf);

    T mn = inf;
    int mu = -1;

    rep(u, 0, n) for(auto [v, w] : g[u]){
        if(u == root || v != root || d[u] >= inf || w >= inf) continue;
        if(mn <= d[u] + w) continue;
        mn = d[u] + w;
        mu = u;
    }
    if(mn == inf) return {inf, {}};

    vector<int> path;
    path.push_back(root);

    stack<int> st;
    int v = mu;
    while(v != root) st.push(v), v = p[v];
    while(!st.empty()) path.push_back(st.top()), st.pop();

    return {mn, path};
}
template<class T> pair<T, vector<int>> shortest_cycle_directed_all(const vector<vector<pair<int, T>>>& g, T inf = numeric_limits<T>::max()){
    T mn = inf;
    vector<int> path;
    rep(i, 0, siz(g)){
        auto [m, p] = shortest_cycle_directed(g, i, inf);
        if(mn > m) mn = m, path = p;
    }
    return {mn, path};
}

void _main() {
    int T, N, M;
    cin >> T >> N >> M;
    constexpr auto inf = numeric_limits<ll>::max();
    vector g(N, vector<pair<int, ll>>());
    rep(i, 0, M){
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        g[u].push_back({v, w});
        if(T == 0) g[v].push_back({u, w});
    }

    if(T == 0){
        auto [mn, path] = shortest_cycle_undirected_all(g, inf);
        outif(mn < inf, mn, -1);
    }
    else{
        auto [mn, path] = shortest_cycle_directed_all(g, inf);
        outif(mn < inf, mn, -1);
    }
}

signed main() { 
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15); cerr << fixed << setprecision(15);
    _main();
}

yukicoder

結果

テストケース

ソースコード