結果

問題 No.114 遠い未来
ユーザー 👑 colognecologne
提出日時 2023-06-14 13:44:01
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,010 ms / 5,000 ms
コード長 3,120 bytes
コンパイル時間 1,996 ms
コンパイル使用メモリ 125,000 KB
実行使用メモリ 8,880 KB
最終ジャッジ日時 2023-09-05 02:07:52
合計ジャッジ時間 7,711 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 436 ms
8,820 KB
testcase_02 AC 173 ms
4,384 KB
testcase_03 AC 32 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 472 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 4 ms
4,380 KB
testcase_10 AC 55 ms
4,804 KB
testcase_11 AC 149 ms
6,040 KB
testcase_12 AC 437 ms
8,868 KB
testcase_13 AC 437 ms
8,880 KB
testcase_14 AC 507 ms
4,380 KB
testcase_15 AC 1,010 ms
4,380 KB
testcase_16 AC 222 ms
4,380 KB
testcase_17 AC 196 ms
4,380 KB
testcase_18 AC 228 ms
4,376 KB
testcase_19 AC 115 ms
4,376 KB
testcase_20 AC 34 ms
4,376 KB
testcase_21 AC 8 ms
4,380 KB
testcase_22 AC 9 ms
4,376 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 2 ms
4,380 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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