結果

問題 No.1690 Power Grid
コンテスト
ユーザー atree
提出日時 2021-09-24 22:41:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 231 ms / 3,000 ms
コード長 4,208 bytes
コンパイル時間 2,722 ms
コンパイル使用メモリ 219,088 KB
最終ジャッジ日時 2025-01-24 17:36:09
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define overload3(_NULL, _1, _2, name, ...) name
#define rep1(i, n) for (remove_const_t<remove_reference_t<decltype(n)>> i = 0; i < (n); i++)
#define rep2(i, a, b) for (remove_const_t<remove_reference_t<decltype(a)>> i = a; i < (b); i++)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#if __has_include(<debug.hpp>)
#    include <debug.hpp>
#else
#    define dbg(...) (void(0))
#endif
template<class T> void drop(const T &x) {
    cout << x << "\n";
    exit(0);
}
template<class T> bool chmax(T &a, const T &b) { return a < b and (a = b, true); }
template<class T> bool chmin(T &a, const T &b) { return a > b and (a = b, true); }
using i64 = long long;
using usize = size_t;
using size_type = usize;

/**
 * @brief Floyd Warshall Algorithm / 負辺を許す全点対最短経路問題
 * @docs docs/floyd_warshall.md
 */

template<typename T> vector<vector<T>> floyd_warshall(vector<vector<pair<size_type, T>>> const &graph) {
    const size_type n = size(graph);
    constexpr T INF = numeric_limits<T>::max();
    vector<vector<T>> dp(n, vector<T>(n, INF));
    rep(i, n) {
        dp[i][i] = 0;
        for (const auto [to, cost]: graph[i]) dp[i][to] = cost;
    }
    rep(k, n) rep(i, n) rep(j, n) if (dp[i][k] < INF and dp[k][j] < INF) chmin(dp[i][j], dp[i][k] + dp[k][j]);
    rep(i, n) if (dp[i][i] < 0) return {};
    return dp;
}

/**
 * @brief Union Find
 * @docs docs/union_find.md
 */

struct UnionFind {
    size_type n;
    vector<int> node;
    explicit UnionFind(const size_type n): n(n), node(n, -1) {}
    bool unite(size_type u, size_type v) {
        u = root(u), v = root(v);
        if (u == v) return false;
        if (node[u] > node[v]) swap(u, v);
        node[u] += node[v];
        node[v] = (int) u;
        return true;
    }
    size_type root(size_type v) { return node[v] < 0 ? v : node[v] = (int) root(node[v]); }
    size_type size(size_type v) { return (size_type) -node[root(v)]; }
    bool same(size_type u, size_type v) { return root(u) == root(v); }
    vector<vector<size_type>> group() {
        vector ret(n, vector<size_type>{});
        rep(i, n) ret[root(i)].push_back(i);
        ret.erase(remove_if(begin(ret), end(ret), [&](const auto &ri) { return empty(ri); }));
        return ret;
    }
};

/**
 * @brief Kruskal's Algorithm
 */

template<typename T> vector<tuple<T, size_type, size_type>> kruskal(const usize n, const usize k, vector<tuple<T, size_type, size_type>> const &edges) {
    using Edge = tuple<T, usize, usize>;
    UnionFind uf(n);
    vector<Edge> ret{};
    for (const auto [cost, u, v]: edges) {
        if (not uf.same(u, v)) {
            ret.emplace_back(Edge{ cost, u, v });
            uf.unite(u, v);
        }
        if (size(ret) + 1 == k) break;
    }
    return ret;
}

int main() {
    usize n, m, k;
    cin >> n >> m >> k;
    vector<i64> a(n);
    for (auto &&ai: a) cin >> ai;
    vector graph(n, vector<pair<usize, i64>>{});
    rep(_, m) {
        usize x, y;
        i64 z;
        cin >> x >> y >> z;
        graph[--x].emplace_back(--y, z);
        graph[y].emplace_back(x, z);
    }
    const auto dist = floyd_warshall(graph);
    using bit_t = int;
    constexpr i64 INF = numeric_limits<i64>::max();

    i64 ans = INF;
    for (bit_t x = (1 << k) - 1; x < (1 << n);) {
        i64 cost = 0;
        rep(i, n) if (x & (1 << i)) cost += a[i];
        using edge_t = tuple<i64, usize, usize>;
        vector<edge_t> sub_graph{};
        rep(i, n) if (x & (1 << i)) {
            rep(j, n) if (x & (1 << j) and dist[i][j] != INF) sub_graph.emplace_back(dist[i][j], i, j);
        }
        sort(begin(sub_graph), end(sub_graph));
        const auto mst = kruskal(n, k, sub_graph);
        cost += accumulate(begin(mst), end(mst), 0ll, [](i64 acc, auto e) { return acc + get<0>(e); });
        chmin(ans, cost);
        bit_t t = x | (x - 1);
        x = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(x) + 1));
    }
    cout << ans << "\n";
}

struct IOSetup {
    IOSetup() noexcept {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;
0