結果

問題 No.114 遠い未来
ユーザー maine_honzuki
提出日時 2020-05-15 22:37:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,146 bytes
コンパイル時間 2,007 ms
コンパイル使用メモリ 185,040 KB
実行使用メモリ 9,088 KB
最終ジャッジ日時 2024-09-19 11:43:19
合計ジャッジ時間 14,349 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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;
        }
        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]);
                }
            }
            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]);
        }
        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) {
            ans = min(ans, krs.solve(bit));
            krs.reset();
        }
        cout << ans << endl;
    }
}
0