結果

問題 No.114 遠い未来
ユーザー maine_honzukimaine_honzuki
提出日時 2020-05-15 22:26:59
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,060 bytes
コンパイル時間 1,942 ms
コンパイル使用メモリ 186,504 KB
実行使用メモリ 14,024 KB
最終ジャッジ日時 2024-09-19 11:17:59
合計ジャッジ時間 18,709 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 25 ms
6,820 KB
testcase_01 AC 1,245 ms
9,216 KB
testcase_02 WA -
testcase_03 AC 161 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 4 ms
6,944 KB
testcase_06 AC 2,458 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 7 ms
6,944 KB
testcase_10 AC 123 ms
6,940 KB
testcase_11 AC 380 ms
6,944 KB
testcase_12 AC 1,254 ms
9,088 KB
testcase_13 AC 1,252 ms
9,088 KB
testcase_14 AC 2,598 ms
6,940 KB
testcase_15 TLE -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template <typename T>
class Kruskal {
    vector<int> data;
    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) {
        edges.reserve(n);
        data.assign(n, -1);
    }
    void add_edge(int from, int to, T cost = 1) {
        edges.emplace_back(from, to, cost);
    }
    T build() {
        sort(edges.begin(), edges.end(), [](const edge& a, const edge& b) {
            return a.cost < b.cost;
        });
        T ret = 0;
        for (auto& e : edges) {
            if (unite(e.from, e.to))
                ret += e.cost;
        }
        return ret;
    }
};

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]);
                }
            }
            if (mask == (1 << t) - 1) break;
            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]);
        }
        for (long long bit = mask; bit < (1ll << N); bit = (bit + 1) | mask) {
            Kruskal<int> krs(N);
            for (int i = 0; i < M; i++) {
                if ((bit & (1ll << a[i])) && (bit & (1ll << b[i]))) {
                    krs.add_edge(a[i], b[i], c[i]);
                    krs.add_edge(b[i], a[i], c[i]);
                }
            }
            ans = min(ans, krs.build());
        }
        cout << ans << endl;
    }
}
0