結果

問題 No.114 遠い未来
コンテスト
ユーザー cologne
提出日時 2023-06-14 13:44:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 956 ms / 5,000 ms
コード長 3,120 bytes
コンパイル時間 1,615 ms
コンパイル使用メモリ 124,208 KB
実行使用メモリ 9,216 KB
最終ジャッジ日時 2024-06-22 23:03:35
合計ジャッジ時間 6,934 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cinttypes>
#include <iostream>
#include <numeric>
#include <tuple>
#include <vector>

struct DisjointSet
{
    std::vector<int> par;
    DisjointSet(int N) : par(N)
    {
        Reset();
    }
    void Reset()
    {
        std::iota(par.begin(), par.end(), 0);
    }
    int Find(int a)
    {
        if (a == par[a])
            return a;
        par[a] = Find(par[a]);
        return par[a];
    }
    bool Union(int a, int b)
    {
        a = Find(a);
        b = Find(b);
        par[a] = b;
        return a != b;
    }
};

int main()
{
    int N, M, T;
    std::cin >> N >> M >> T;
    std::vector<std::tuple<int, int, int>> E(M);
    for (auto &[c, a, b] : E)
    {
        std::cin >> a >> b >> c;
        b--;
        a--;
    }

    std::vector<int> V(T);
    for (int &v: V)
    {
        std::cin >> v;
        v--;
    }

    std::vector<std::vector<int>> D(N, std::vector<int>(N, std::numeric_limits<int>::max() / 2));
    for (int i = 0; i < N; i++)
        D[i][i] = 0;
    for (auto [c, a, b] : E)
        D[a][b] = D[b][a] = c;
    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]);

    if (T <= 3 * N / 7)
    {
        std::vector<std::vector<int>> DP(1 << T, std::vector<int>(N, std::numeric_limits<int>::max() / 2));
        for (int i = 0; i < T; ++i)
            for (int j = 0; j < N; ++j)
                DP[1 << i][j] = D[V[i]][j];
        for (int v = 1; v < (1 << T); ++v)
        {
            for (int m1 = 0; (m1 = (m1 - v) & v);)
            {
                int m2 = v - m1; if(m2 < m1) break;
                for (int i = 0; i < N; i++)
                    DP[v][i] = std::min(DP[v][i], DP[m1][i] + DP[m2][i]);
            }
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    DP[v][i] = std::min(DP[v][i], DP[v][j] + D[j][i]);
        }
        std::cout << *std::min_element(DP.back().begin(), DP.back().end()) << std::endl;
    }
    else
    {
        std::sort(E.begin(), E.end());
        std::vector<bool> target(N);

        for(int v: V) target[v] = true;
        std::vector<int> Vc;
        for(int i=0; i<N; i++) if(!target[i]) Vc.push_back(i);

        DisjointSet ds(N); int ans = std::numeric_limits<int>::max();
        for(int i=0; i<(1<<(N-T)); i++)
        {
            ds.Reset();
            int comp = T;
            for(int j=0; j<N-T; j++)
            {
                if(i&(1<<j))
                {
                    target[Vc[j]] = true;
                    comp++;
                }
                else target[Vc[j]] = false;
            }


            int res = 0;
            for(auto [c, a, b]: E)
            {
                if(target[a] && target[b] && ds.Union(a, b))
                {
                    res += c;
                    if(--comp == 1)
                        break;
                }
            }
            if(comp == 1)
                ans = std::min(ans, res);
        }
        std::cout << ans << std::endl;
    }
}
0