結果

問題 No.114 遠い未来
ユーザー 👑 colognecologne
提出日時 2022-02-03 00:35:23
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,120 bytes
コンパイル時間 3,297 ms
コンパイル使用メモリ 114,688 KB
最終ジャッジ日時 2024-04-27 04:03:50
合計ジャッジ時間 3,720 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:54:65: error: no member named 'numeric_limits' in namespace 'std'
   54 |     std::vector<std::vector<int>> D(N, std::vector<int>(N, std::numeric_limits<int>::max() / 2));
      |                                                            ~~~~~^
main.cpp:54:83: error: expected '(' for function-style cast or type construction
   54 |     std::vector<std::vector<int>> D(N, std::vector<int>(N, std::numeric_limits<int>::max() / 2));
      |                                                                                ~~~^
main.cpp:54:86: error: no member named 'max' in the global namespace
   54 |     std::vector<std::vector<int>> D(N, std::vector<int>(N, std::numeric_limits<int>::max() / 2));
      |                                                                                    ~~^
main.cpp:66:75: error: no member named 'numeric_limits' in namespace 'std'
   66 |         std::vector<std::vector<int>> DP(1 << T, std::vector<int>(N, std::numeric_limits<int>::max() / 2));
      |                                                                      ~~~~~^
main.cpp:66:93: error: expected '(' for function-style cast or type construction
   66 |         std::vector<std::vector<int>> DP(1 << T, std::vector<int>(N, std::numeric_limits<int>::max() / 2));
      |                                                                                          ~~~^
main.cpp:66:96: error: no member named 'max' in the global namespace
   66 |         std::vector<std::vector<int>> DP(1 << T, std::vector<int>(N, std::numeric_limits<int>::max() / 2));
      |                                                                                              ~~^
main.cpp:93:43: error: no member named 'numeric_limits' in namespace 'std'
   93 |         DisjointSet ds(N); int ans = std::numeric_limits<int>::max();
      |                                      ~~~~~^
main.cpp:93:61: error: expected '(' for function-style cast or type construction
   93 |         DisjointSet ds(N); int ans = s

ソースコード

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