結果

問題 No.1320 Two Type Min Cost Cycle
ユーザー K UK U
提出日時 2024-05-17 20:43:30
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,282 bytes
コンパイル時間 5,466 ms
コンパイル使用メモリ 283,456 KB
実行使用メモリ 72,308 KB
最終ジャッジ日時 2024-12-20 13:00:18
合計ジャッジ時間 65,016 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
42,904 KB
testcase_01 AC 12 ms
43,248 KB
testcase_02 AC 13 ms
43,136 KB
testcase_03 AC 13 ms
43,116 KB
testcase_04 AC 13 ms
72,308 KB
testcase_05 AC 14 ms
43,148 KB
testcase_06 AC 15 ms
43,112 KB
testcase_07 AC 52 ms
43,100 KB
testcase_08 AC 97 ms
43,144 KB
testcase_09 TLE -
testcase_10 AC 63 ms
43,144 KB
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 AC 52 ms
43,136 KB
testcase_15 AC 66 ms
72,116 KB
testcase_16 AC 15 ms
43,040 KB
testcase_17 AC 35 ms
43,312 KB
testcase_18 AC 34 ms
43,272 KB
testcase_19 TLE -
testcase_20 AC 25 ms
43,052 KB
testcase_21 TLE -
testcase_22 AC 12 ms
43,132 KB
testcase_23 AC 12 ms
43,204 KB
testcase_24 AC 12 ms
72,048 KB
testcase_25 AC 12 ms
43,032 KB
testcase_26 AC 12 ms
42,908 KB
testcase_27 AC 12 ms
72,204 KB
testcase_28 AC 52 ms
43,076 KB
testcase_29 TLE -
testcase_30 AC 14 ms
42,928 KB
testcase_31 AC 1,659 ms
36,140 KB
testcase_32 AC 12 ms
36,184 KB
testcase_33 TLE -
testcase_34 TLE -
testcase_35 AC 13 ms
36,152 KB
testcase_36 AC 13 ms
36,220 KB
testcase_37 AC 12 ms
36,216 KB
testcase_38 AC 14 ms
36,260 KB
testcase_39 AC 13 ms
36,208 KB
testcase_40 AC 12 ms
36,156 KB
testcase_41 AC 12 ms
36,128 KB
testcase_42 AC 12 ms
36,084 KB
testcase_43 AC 99 ms
36,204 KB
testcase_44 AC 54 ms
36,148 KB
testcase_45 TLE -
testcase_46 AC 1,395 ms
36,220 KB
testcase_47 TLE -
testcase_48 TLE -
testcase_49 AC 687 ms
36,264 KB
testcase_50 AC 12 ms
36,100 KB
testcase_51 AC 12 ms
36,132 KB
testcase_52 AC 1,073 ms
36,244 KB
testcase_53 AC 497 ms
36,284 KB
testcase_54 TLE -
testcase_55 TLE -
testcase_56 TLE -
testcase_57 TLE -
testcase_58 TLE -
testcase_59 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx") // 自動ベクトル化（ループの高速化）
#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;

using Type = ll;
constexpr int MAX_N = 2048;
int N;
Type g[MAX_N][MAX_N];

// 最短路木 - 密グラフバージョン O(N^2)
// 戻り値: d[v]=最短距離(重み), p[v]=親頂点(rootの場合、-1), l[v]=通る経路の色分け。最初の頂点(root直下の頂点番号) 
tuple<vector<Type>, vector<int>, vector<int>> shortest_path_tree(int root, Type inf = numeric_limits<Type>::max()){
    vector<Type> d(N, inf);
    vector<int> p(N, -1), l(N, -1);
    vector<bool> done(N);
    d[root] = 0;
    while(true){
        int v = -1;
        Type mn = inf;
        rep(i, 0, N) if(!done[i] && d[i] < mn) v = i, mn = d[i];
        if(v == -1) break;
        done[v] = true;
        rep(i, 0, N){
            bool f = done[i] || i == v || g[v][i] >= inf || d[i] <= mn + g[v][i];
            d[i] = f ? d[i] : mn + g[v][i];
            p[i] = f ? p[i] : v;
            l[i] = f ? l[i] : v == root ? i : l[v];
        }
    }
    return {d, p, l};
}

// 無向グラフ 最小サイクル - 密グラフバージョン O(N^2)
pair<Type, vector<int>> shortest_cycle_undirected(int root, Type inf = numeric_limits<Type>::max()){
    auto [d, p, l] = shortest_path_tree(root, inf);

    Type mn = inf;
    int mu = -1, mv = -1;
    rep(u, 0, N){
        if(u == root || d[u] >= inf) continue;
        rep(v, u + 1, N){
            bool f = v == root || l[u] == l[v] || d[v] >= inf || g[u][v] >= inf || mn <= d[u] + d[v] + g[u][v];
            mn = f ? mn : d[u] + d[v] + g[u][v];
            mu = f ? mu : u;
            mv = f ? mv : v;
        }
    } 
    if(mn == inf) return {inf, {}};

    vector<int> path;
    int v = mu;
    while(v != root) path.push_back(v), v = p[v];
    path.push_back(root);
    reverse(all(path));
    v = mv;
    while(v != root) path.push_back(v), v = p[v];

    return {mn, path};
}
pair<Type, vector<int>> shortest_cycle_undirected_all(Type inf = numeric_limits<Type>::max()){
    Type mn = inf;
    vector<int> path;
    rep(i, 0, N){
        auto [m, p] = shortest_cycle_undirected(i, inf);
        if(mn > m) mn = m, path = p;
    }
    return {mn, path};
}

// 有向グラフ 最小サイクル - 密グラフバージョン O(N^2)
pair<Type, vector<int>> shortest_cycle_directed(int root, Type inf = numeric_limits<Type>::max()){
    auto [d, p, l] = shortest_path_tree(root, inf);

    Type mn = inf;
    int v = -1;
    rep(i, 0, N){
        bool f = i == root || d[i] >= inf || g[i][root] >= inf || mn <= d[i] + g[i][root];
        mn = f ? mn : d[i] + g[i][root];
        v = f ? v : i;
    }
    if(mn == inf) return {inf, {}};

    vector<int> path;
    while(v != root) path.push_back(v), v = p[v];
    path.push_back(root);
    reverse(all(path));

    return {mn, path};
}
pair<Type, vector<int>> shortest_cycle_directed_all(Type inf = numeric_limits<Type>::max()){
    Type mn = inf;
    vector<int> path;
    rep(i, 0, N){
        auto [m, p] = shortest_cycle_directed(i, inf);
        if(mn > m) mn = m, path = p;
    }
    return {mn, path};
}

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

    if(T == 0){
        auto [mn, path] = shortest_cycle_undirected_all(inf);
        outif(mn < inf, mn, -1);
    }
    else{
        auto [mn, path] = shortest_cycle_directed_all(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();
}
0