結果

問題 No.114 遠い未来
コンテスト
ユーザー cologne
提出日時 2022-02-03 00:35:23
言語 C++17(clang)
(clang++ 22.1.2 + boost 1.89.0)
コンパイル:
clang++ -O2 -lm -std=c++1z -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,120 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,280 ms
コンパイル使用メモリ 111,304 KB
最終ジャッジ日時 2026-05-10 07:12:18
合計ジャッジ時間 4,935 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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:84: error: no member named 'max' in the global namespace; did you mean 'std::max'?
   54 |     std::vector<std::vector<int>> D(N, std::vector<int>(N, std::numeric_limits<int>::max() / 2));
      |                                                                                    ^~~~~
      |                                                                                    std::max
/usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/algorithmfwd.h:403:5: note: 'std::max' declared here
  403 |     max(const _Tp&, const _Tp&);
      |     ^
main.cpp:54:86: error: no matching function for call to 'max'
   54 |     std::vector<std::vector<int>> D(N, std::vector<int>(N, std::numeric_limits<int>::max() / 2));
      |                                                                                      ^~~
/usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/algorithmfwd.h:403:5: note: candidate function template not viable: requires 2 arguments, but 0 were provided
  403 |     max(const _Tp&, const _Tp&);
      |     ^   ~~~~~~~~~~~~~~~~~~~~~~
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 constr

ソースコード

diff #
raw source code 

#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