結果

問題 No.114 遠い未来
ユーザー maine_honzukimaine_honzuki
提出日時 2020-05-15 23:04:34
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,907 ms / 5,000 ms
コード長 4,285 bytes
コンパイル時間 2,068 ms
コンパイル使用メモリ 186,228 KB
実行使用メモリ 9,152 KB
最終ジャッジ日時 2023-10-19 16:42:38
合計ジャッジ時間 14,663 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
4,348 KB
testcase_01 AC 1,355 ms
9,152 KB
testcase_02 AC 138 ms
4,348 KB
testcase_03 AC 30 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 5 ms
4,348 KB
testcase_06 AC 513 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 8 ms
4,348 KB
testcase_10 AC 133 ms
4,992 KB
testcase_11 AC 413 ms
6,276 KB
testcase_12 AC 1,372 ms
9,152 KB
testcase_13 AC 1,366 ms
9,152 KB
testcase_14 AC 492 ms
4,348 KB
testcase_15 AC 2,907 ms
4,348 KB
testcase_16 AC 232 ms
4,348 KB
testcase_17 AC 309 ms
4,348 KB
testcase_18 AC 1,732 ms
4,348 KB
testcase_19 AC 127 ms
4,348 KB
testcase_20 AC 214 ms
4,348 KB
testcase_21 AC 10 ms
4,348 KB
testcase_22 AC 13 ms
4,348 KB
testcase_23 AC 2 ms
4,348 KB
testcase_24 AC 5 ms
4,348 KB
testcase_25 AC 2 ms
4,348 KB
testcase_26 AC 2 ms
4,348 KB
testcase_27 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template <typename T>
class Kruskal {
    vector<int> data;
    int N;
    bool unite(int x, int y) {
        x = root(x), y = root(y);
        if (x == y)
            return (false);
        if (data[x] > data[y])
            swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return (true);
    }
    int root(int k) {
        if (data[k] < 0)
            return (k);
        return (data[k] = root(data[k]));
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    int size(int k) {
        return (-data[root(k)]);
    }
    //
public:
    struct edge {
        int from, to;
        T cost;
        bool used;
        edge(int from, int to, T cost) : from(from), to(to), cost(cost), used(false) {}
    };
    vector<edge> edges;
    Kruskal(int n) : N(n) {
        data.assign(n, -1);
    }
    void add_edge(int from, int to, T cost = 1) {
        edges.emplace_back(from, to, cost);
    }
    void build() {
        sort(edges.begin(), edges.end(), [](const edge& a, const edge& b) {
            return a.cost < b.cost;
        });
    }
    T solve(long long bit) {
        T ret = 0;
        for (auto& e : edges) {
            if (bit & (1ll << e.from) && bit & (1ll << e.to))
                if (unite(e.from, e.to))
                    ret += e.cost;
        }
        if (size(__builtin_ffsll(bit) - 1) != __builtin_popcountll(bit)) {
            return T(-1);
        } else
            return ret;
    }
    void reset() {
        data.assign(N, -1);
    }
};

template <typename T>
struct Steiner {
    vector<vector<T>> dist;
    vector<vector<T>> dp;
    vector<int> terminal;
    const T inf = numeric_limits<T>::max() / 10;
    int N;
    Steiner(int n) : N(n), dist(n, vector<T>(n)) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i != j)
                    dist[i][j] = inf;
            }
        }
    }
    void add_edge(int u, int v, T cost) {
        dist[u][v] = cost;
        dist[v][u] = cost;
    }
    void add_terminal(int u) {
        terminal.emplace_back(u);
    }
    T build() {
        int t = (int)terminal.size();
        if (t == 0) return (T)0;
        dp.resize((1 << t), vector<T>(N, inf));
        for (int i = 0; i < t; i++) {
            dp[(1 << i)][terminal[i]] = 0;
        }
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        for (int mask = 0; mask < (1 << t); mask++) {
            for (int i = 0; i < N; i++) {
                for (int bit = mask; bit > 0; bit = (bit - 1) & mask) {
                    dp[mask][i] = min(dp[mask][i], dp[bit][i] + dp[bit ^ mask][i]);
                }
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    dp[mask][i] = min(dp[mask][i], dp[mask][j] + dist[j][i]);
                }
            }
        }
        return dp[(1 << t) - 1][terminal[0]];
    }
};


int main() {
    int N, M, T, a[1500], b[1500], c[1500], v[40];
    cin >> N >> M >> T;
    for (int i = 0; i < M; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--;
        b[i]--;
    }
    for (int i = 0; i < T; i++) {
        cin >> v[i];
        v[i]--;
    }
    if (T < 16) {
        Steiner<int> st(N);
        for (int i = 0; i < M; i++) {
            st.add_edge(a[i], b[i], c[i]);
        }
        for (int i = 0; i < T; i++) {
            st.add_terminal(v[i]);
        }
        cout << st.build() << endl;
    } else {
        int ans = 1e7;
        long long mask = 0;
        for (int i = 0; i < T; i++) {
            mask |= (1ll << v[i]);
        }
        Kruskal<int> krs(N);
        for (int i = 0; i < M; i++) {
            krs.add_edge(a[i], b[i], c[i]);
            krs.add_edge(b[i], a[i], c[i]);
        }
        krs.build();
        for (long long bit = mask; bit < (1ll << N); bit = (bit + 1) | mask) {
            int tmp = krs.solve(bit);
            krs.reset();
            if (tmp == -1) continue;
            ans = min(ans, tmp);
        }
        cout << ans << endl;
    }
}
0