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

• 問題: No.114 遠い未来
• ユーザー: usuke ta
• 提出日時: 2026-06-30 22:50:28
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1,259 ms / 5,000 ms
• コード長: 4,958 bytes
• コンパイル時間: 4,797 ms
• コンパイル使用メモリ: 393,212 KB
• 実行使用メモリ: 19,840 KB
• 最終ジャッジ日時: 2026-06-30 22:50:48
• 合計ジャッジ時間: 12,855 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

//  ===== ライブラリインクルード =====
#include <bit>
#include <bits/stdc++.h>
#include <queue>
#include <ratio>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

//  ===== 型の省略名定義 =====
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using vc = vector<char>;
using vvc = vector<vector<char>>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vvpii = vector<vector<pii>>;
using vpll = vector<pll>;
using vvpll = vector<vector<pll>>;
using vs = vector<string>;

//  ===== 略記用マクロ =====
#define rep(i, n) for (auto i = std::decay_t<decltype(n)>{0}; i < (n); ++i)
#define rrep(i, n) for (auto i = (n); i-- > 0;)
#define nfor(i, l, r) for (auto i = (l); i < (r); ++i)
#define rnfor(i, l, r) for (auto i = (r); i-- > (l); )
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

//  ===== 無限大定数 =====
constexpr int INF = 1e9 + 10;
constexpr ll LINF = 4e18 + 10;
constexpr i128 inf128 = 1e37 + 10;

//  ===== 入出力 =====
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p)
{return os << p.first << " " << p.second;}

template <typename t>
concept hasval = requires(t v) {{ v.val() } -> convertible_to<long long>;};
ostream& operator<<(ostream& os, hasval auto v) {return os << v.val();}

template <class t>
void print_vector(const vector<t>& v, const string& sep = "\n", bool omit_last = false)
{
    int siz = (int)v.size();
    rep(i, siz)
    {
        cout << v[i];
        if(!(omit_last && i == siz - 1)) cout << sep;
    }
}
void yes_no(bool ans, bool omit_break = false) {cout << (ans ? "yes" : "no") << (omit_break ? "" : "\n");}
template<typename t> t ninf(t ans, t inf_val) {return (ans >= inf_val ? -1 : ans);}
int ninf(int ans) {return (ans >= INF ? -1 : ans);}
ll ninf(ll ans) {return (ans >= LINF ? -1 : ans);}

//  ===== 汎用関数 =====
template <class t, class u> bool chmax(t &a, u b){ if(a<b){a=b; return true;} return false;}
template <class t, class u> bool chmin(t &a, u b){ if(a>b){a=b; return true;} return false;}
template <class t> void dedup(vector<t>& v) {v.erase(unique(all(v)), v.end());}

//  ========== テンプレ終わり ==========

using mint = modint998244353;
using vm = vector<mint>;
using vvm = vector<vm>;



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, t;
    cin >> n >> m >> t;

    vvpii g(n);
    rep(i, m)
    {
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    vi v(t);
    for(int& x : v) cin >> x, --x;
    sort(all(v));

    if(t <= 16)
    {
        vvi dp(1<<t, vi(n, INF));
        rep(i, t) dp[1<<i][v[i]] = 0;
        vvc determined(1<<t, vc(n, false));
        priority_queue<pii, vpii, greater<pii>> pq;
        nfor(s, 1, 1<<t)
        {
            for(int a = (s-1)&s; a; a = (a-1)&s)
            {
                int b = s ^ a;
                rep(i, n) chmin(dp[s][i], dp[a][i] + dp[b][i]);
            }

            rep(i, n)
            {
                if(dp[s][i] == INF) continue;
                pq.emplace(dp[s][i], i);
            }

            while(!pq.empty())
            {
                auto [d, u] = pq.top();
                pq.pop();
                if(determined[s][u]) continue;

                dp[s][u] = d;
                determined[s][u] = true;

                for(auto [v, c] : g[u])
                {
                    if(d + c >= dp[s][v]) continue;
                    dp[s][v] = d + c;
                    pq.emplace(d + c, v);
                }
            }
        }

        cout << dp[(1<<t)-1][v[0]] << "\n";
        return 0;
    }
    else
    {
        struct edge {int u, v, c;};
        vector<edge> e;
        rep(u, n) for(auto [v, c] : g[u]) e.push_back({u, v, c});
        sort(all(e), [](edge a, edge b){return a.c < b.c;});

        auto spanning_tree = [&](ll S) -> ll
        {
            int ans = 0;
            int group = popcount((ull)S);
            dsu uf(n);
            for(auto [u, v, c] : e)
            {
                if(!(S & (1LL<<u)) || !(S & (1LL<<v)) || uf.same(u, v)) continue;

                ans += c;
                uf.merge(u, v);
                --group;
                if(group == 1) return ans;
            }
            return INF;
        };
    
        ll T = 0;
        for(int x : v) T |= 1LL<<x;

        ll R = ((1LL<<n)-1) ^ T;
        int ans = INF;
        for(ll C = R; ; C = (C-1)&R)
        {
            chmin(ans, spanning_tree(T | C));
            if(C == 0) break;
        }

        cout << ans << "\n";
        return 0;
    }
}