#1181693 (C++23) No.114 遠い未来

• 問題: No.114 遠い未来
• ユーザー: T1610
• 提出日時: 2026-08-31 00:27:17
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 3,682 ms / 5,000 ms
• コード長: 5,003 bytes
• コンパイル時間: 4,940 ms
• コンパイル使用メモリ: 390,536 KB
• 実行使用メモリ: 9,780 KB
• 最終ジャッジ日時: 2026-08-31 00:27:43
• 合計ジャッジ時間: 16,487 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 25

ソースコード

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
#define rep(i, n) REP(i, 0, n)
#define REP(i, s, e) for (int i = (s); i < (int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for (int i = (int)(s - 1); i >= (int)(e); i--)
#define all(r) r.begin(), r.end()
#define rall(r) r.rbegin(), r.rend()

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

template <typename T, typename U>
T chmax(T& a, const U& b) {
    if (a >= b) return false;
    a = b;
    return true;
}
template <typename T, typename U>
T chmin(T& a, const U& b) {
    if (a <= b) return false;
    a = b;
    return true;
}

void yes_no(bool f, string yes = "Yes", string no = "No") { cout << (f ? yes : no) << "\n"; }

const long long INF = 1e18; // オーバーフローしない十分大きな値

/**
 * @brief Dreyfus-Wagner法によるシュタイナー木の最小コスト計算
 *
 * @param V 頂点数
 * @param terminals ターミナルとなる頂点のリスト (0-indexed)
 * @param d グラフの隣接行列表現 (d[u][v]: 辺のコスト, 辺がない場合はINF, d[i][i] = 0)
 * @return long long シュタイナー木の最小コスト
 */
long long steiner_tree(int V, const vector<int>& terminals, const vector<vector<long long>>& d) {
    int K = terminals.size();
    if (K == 0) return 0;
    if (K == 1) return 0;

    // 1. 全点対最短経路をWarshall-Floyd法で求める
    vector<vector<long long>> dist = d;
    for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i) {
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < V; ++j) {
                if (dist[k][j] == INF) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    // 2. DPテーブルの初期化
    // dp[S][v] : ターミナルの部分集合 S を含み、頂点 v で接続されるシュタイナー木の最小コスト
    vector<vector<long long>> dp(1 << K, vector<long long>(V, INF));

    // サイズが 1 の部分集合の初期化
    for (int i = 0; i < K; ++i) {
        for (int v = 0; v < V; ++v) {
            dp[1 << i][v] = dist[terminals[i]][v];
        }
    }

    // 3. DPの更新 (Sの要素数が少ない順に計算される)
    for (int S = 1; S < (1 << K); ++S) {
        // S の要素数が 1 の場合はすでに計算済みのためスキップ
        if (!(S & (S - 1))) continue;

        // a. 部分木同士の結合
        // S の真部分集合 T をビット演算で高速に列挙するテクニック
        for (int T = (S - 1) & S; T > 0; T = (T - 1) & S) {
            for (int v = 0; v < V; ++v) {
                if (dp[T][v] != INF && dp[S ^ T][v] != INF) {
                    dp[S][v] = min(dp[S][v], dp[T][v] + dp[S ^ T][v]);
                }
            }
        }

        // b. 他の頂点を経由する場合の緩和 (最短経路を用いて拡張)
        for (int v = 0; v < V; ++v) {
            if (dp[S][v] == INF) continue;
            for (int u = 0; u < V; ++u) {
                if (dist[v][u] == INF) continue;
                dp[S][u] = min(dp[S][u], dp[S][v] + dist[v][u]);
            }
        }
    }

    // 4. 全てのターミナルを含む最小コストを取得
    // どの頂点 v を起点としてもよいので、その中での最小値を探す
    long long ans = INF;
    for (int v = 0; v < V; ++v) {
        ans = min(ans, dp[(1 << K) - 1][v]);
    }

    return ans;
}

void solve() {
    int n, m, t;
    cin >> n >> m >> t;
    vector<vl> d(n, vl(n, INF));
    using T = tuple<ll, int, int>;
    vector<T> es;
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        --a;
        --b;
        d[a][b] = c;
        d[b][a] = c;
        es.emplace_back(c, a, b);
    }
    rep(i, n) d[i][i] = 0;
    vector<int> v(t);
    rep(i, t) cin >> v[i], --v[i];
    if (t < 15) {
        ll ans = steiner_tree(n, v, d);
        cout << ans << "\n";
    } else {
        ll ans = INF;
        sort(all(es));
        vi a;
        rep(i, n) {
            bool f = true;
            rep(j, t) if (v[j] == i) f = false;
            if (f) a.emplace_back(i);
        }
        int sz = a.size();
        rep(ng, 1 << sz) {
            vi use = v;
            rep(i, sz) if ((ng & (1 << i)) == 0) use.emplace_back(a[i]);
            vi rev(n, -1);
            int tot = use.size();
            rep(i, tot) rev[use[i]] = i;
            dsu uf(n);
            ll tmp = 0;
            for (auto&& [w, x, y] : es) {
                if (uf.same(x, y)) continue;
                if (rev[x] == -1 || rev[y] == -1) continue;
                uf.merge(x, y);
                tmp += w;
            }
            if (uf.size(v[0]) == tot) chmin(ans, tmp);
        }
        cout << ans << "\n";
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
    // multi-testcase
    // cin >> t;
    rep(ti, t) solve();
    return 0;
}