結果

問題 No.114 遠い未来
ユーザー codershifthcodershifth
提出日時 2015-10-11 23:37:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,088 ms / 5,000 ms
コード長 6,975 bytes
コンパイル時間 1,789 ms
コンパイル使用メモリ 186,592 KB
実行使用メモリ 6,016 KB
最終ジャッジ日時 2024-07-21 07:02:50
合計ジャッジ時間 8,565 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 24 ms
5,248 KB
testcase_01 AC 918 ms
5,376 KB
testcase_02 AC 294 ms
5,376 KB
testcase_03 AC 47 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 537 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 7 ms
5,376 KB
testcase_10 AC 120 ms
5,376 KB
testcase_11 AC 360 ms
6,016 KB
testcase_12 AC 859 ms
5,376 KB
testcase_13 AC 1,088 ms
5,376 KB
testcase_14 AC 433 ms
5,376 KB
testcase_15 AC 507 ms
5,376 KB
testcase_16 AC 237 ms
5,376 KB
testcase_17 AC 166 ms
5,376 KB
testcase_18 AC 196 ms
5,376 KB
testcase_19 AC 111 ms
5,376 KB
testcase_20 AC 28 ms
5,376 KB
testcase_21 AC 8 ms
5,376 KB
testcase_22 AC 9 ms
5,376 KB
testcase_23 AC 1 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

class UFTree {
    std::vector<int> par_;
    std::vector<int> rank_;
public:
    UFTree(int N) { init(N); }
    UFTree() {}
    ~UFTree() {}

    void init(int N) {
        par_.resize(N);
        rank_.resize(N, 0);
        for (int i = 0; i < N; ++i)
            par_[i] = i;
    }
    int find(int x) {
        if ( par_[x] == x )
            return x;
        else
            return ( par_[x] = find(par_[x]));
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if ( x == y )
            return;
        if ( rank_[x] < rank_[y] )
            par_[x] = y;
        else
        {
            par_[y] = x;
            if ( rank_[x] == rank_[y] )
                ++rank_[x];
        }
    }
    bool same(int x, int y) {
        return (find(x) == find(y));
    }
    int operator[](size_t i) { return find(i); }
};

template <typename T>
class MinSteinerTree
{
public:
    using matrix = std::vector<std::vector<T>>;
    matrix graph_;
    MinSteinerTree() {}
    MinSteinerTree(int n) { init(n); }
    T inf() { return (1<<29); }
    void init(int n)
    {
            graph_.resize(n);
            for (int i = 0; i < n; ++i)
                graph_[i].resize(n,inf());
            for (int i = 0; i < n; ++i)
                graph_[i][i] = 0;
    }
    void add(int u, int v, T c) { graph_[u][v] = graph_[v][u] = c; }
    T solve(const std::vector<T> &t) { return solve(t, graph_); }
    T solve(const std::vector<T> &t,
            const std::vector<std::vector<int>> &g)
    {
            const int n = g.size();
            const int nt = t.size();

            if (nt <= 1)
                return 0;

            matrix d(g); //最短距離
            for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);

            // opt[S][p] := S をターミナルとし p を含む最小シュタイナー木を作成するときのコスト
            matrix opt(1<<nt, std::vector<T>(n, inf()));

            // 各ターミナルから直接つなげる部分を先に計算
            for (int p = 0; p < nt; ++p)
            for (int q = 0; q < n; ++q)
                opt[1<<p][q] = d[t[p]][q];

            // DP で最適コストを計算する。 O(4^|t|*n^2)
            for (int S = 1; S < (1<<nt); ++S)
            {
                if ( !(S & (S-1)) ) // 部分集合がないなら飛ばす
                    continue;
                // S を分割して更新してみる
                for (int p = 0; p < n; ++p)
                for (int E = (S-1)&S; E; E = (E-1)&S) // O(|S|) <= O(2^|t|) (部分集合を回る)
                    opt[S][p] = std::min(opt[S][p], opt[E][p] + opt[S-E][p]);

                // 辺を追加して更新してみる
                for (int p = 0; p < n; ++p)
                for (int q = 0; q < n; ++q)
                    opt[S][p] = std::min(opt[S][p], opt[S][q] + d[p][q]);
            }

            T ans = inf();
            for (int S = 0; S < (1<<nt); ++S)
            for (int q = 0; q < n; ++q)
                ans = std::min(ans, opt[S][q] + opt[((1<<nt)-1)-S][q]);

            return ans;
    }
};

using namespace std;

class TheDistantFuture
{
public:
    void solve(void)
    {
            int N,M,T;
            cin>>N>>M>>T;

            vector<tuple<int,int,int>> edge;
            MinSteinerTree<int> mst(N);
            REP(i,M)
            {
                int a,b,c;
                cin>>a>>b>>c;
                --a,--b;
                mst.add(a,b,c);
                edge.emplace_back(c,a,b); // sort のため cost を先頭に入れておく
            }
            vector<int> t(T);
            REP(i,T)
            {
                int tmp;
                cin>>tmp;
                --tmp;
                t[i] = tmp;
            }
            if (T <= 14)
                cout<<mst.solve(t)<<endl;
            else
            {
                vector<int> idx(N); // index 参照用
                int k = 0;
                REP(v,N)
                {
                    if (find(RANGE(t), v) != t.end())
                        idx[v] = -1;
                    else
                        idx[v] = k++;
                }
                int mincost = (1<<30);

                // T が大きいときは T を除いた残りの頂点のうちどれを使うかの 2^(N-T) 通りを全探索する。
                // kruskal 法
                sort(RANGE(edge)); // cost が小さい順に並べる
                // O(2^(N-T)*M)
                for (int R = 0; R < (1<<(N-T)); ++R)
                {
                    const auto inf = (1<<30);
                    UFTree uft(N); // O(N)
                    vector<bool> used(N,false);
                    int cost = 0;
                    int nR;

                    for (auto e : edge)
                    {
                        int a,b,c;
                        int ia,ib;

                        tie(c,a,b) = e;
                        ia = idx[a];
                        ib = idx[b];

                        // 端点が t にも R にも含まれていないなら飛ばす
                        if ( ia >= 0 && !((1<<ia) & R) )
                            continue;
                        if ( ib >= 0 && !((1<<ib) & R) )
                            continue;

                        // 連結済みなら飛ばす
                        if (uft.same(a,b))
                            continue;
                        uft.unite(a,b);
                        used[a] = used[b] = true;
                        cost += c;
                        // 枝刈り
                        if ( cost > mincost )
                        {
                            cost = inf;
                            break;
                        }
                    }
                    // 出来上がった木が単連結になっているか確認
                    nR = 0;
                    REP(v,N)
                    {
                        // 単連結か？
                        if (used[v] && uft[t[0]] != uft[v])
                            cost = inf;
                        if ((1<<idx[v]) & R)
                            ++nR;
                    }
                    // set(R) u set(t) をカバーしているか？
                    if (nR + T != count(RANGE(used),true))
                        cost = inf;

                    mincost = min(mincost, cost);
                }
                cout<<mincost<<endl;
            }
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new TheDistantFuture();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0