結果

問題 No.114 遠い未来
ユーザー GOTKAKO
提出日時 2025-07-03 23:03:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,932 ms / 5,000 ms
コード長 4,630 bytes
コンパイル時間 3,107 ms
コンパイル使用メモリ 236,864 KB
実行使用メモリ 13,184 KB
最終ジャッジ日時 2025-07-03 23:04:12
合計ジャッジ時間 14,789 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

pair<long long,vector<pair<int,int>>> SteinerTree(const vector<vector<pair<int,long long>>> &Graph,const vector<int> &X){
    //頂点集合Xを含む全域木 O(N3^K+2^K(N+M)logN).
    //return {cost,辺Ui-Vi集合(Ui<Vi)} 連結じゃないならinfを返す.
    //重みが0以下があると多分だめ.
    int N = Graph.size(),K = X.size(),K2 = 1<<K;
    long long inf = 3e18;
    vector<vector<long long>> dist(K2,vector<long long>(N,inf));
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>> Q;
    for(int i=0; i<K; i++) dist.at(1<<i).at(X.at(i)) = 0;
    for(int s=1; s<(K2); s++){
        for(int t=(s-1)&s; t>0; t=(t-1)&s){
            int p = t,q = s^t;
            if(p < q) break;
            for(int i=0; i<N; i++) dist.at(s).at(i) = min(dist.at(s).at(i),dist.at(p).at(i)+dist.at(q).at(i));
        }
        for(int i=0; i<N; i++) if(dist.at(s).at(i) != inf) Q.push({dist.at(s).at(i),i});
        while(Q.size()){
            auto [nowd,pos] = Q.top(); Q.pop();
            if(dist.at(s).at(pos) != nowd) continue;
            for(auto [to,w] : Graph.at(pos)){
                if(nowd+w < dist.at(s).at(to)) dist.at(s).at(to) = nowd+w,Q.push({nowd+w,to});
            }
        }
    }
    long long cost = inf;
    vector<pair<int,int>> edge;
    {
        int pos = min_element(dist.back().begin(),dist.back().end())-dist.back().begin(),S = K2-1;
        cost = dist.at(S).at(pos);
        if(cost == inf) return {inf,{}};
        queue<pair<int,int>> SP; SP.push({S,pos});
        while(SP.size()){
            tie(S,pos) = SP.front(); SP.pop();
            while(true){
                bool cont = false;
                for(auto [to,w] : Graph.at(pos)){
                    if(dist.at(S).at(to)+w == dist.at(S).at(pos)){
                        edge.push_back({min(to,pos),max(to,pos)});
                        cont = true; pos = to;
                        break;
                    }
                }
                if(cont) continue;
                break;
            }
            if(dist.at(S).at(pos) > 0){
                for(int T=(S-1)&S; T>0; T=(T-1)&S){
                    int p = T,q = S^T;
                    if(dist.at(p).at(pos)+dist.at(q).at(pos) == dist.at(S).at(pos)){
                        SP.push({p,pos}),SP.push({q,pos});
                        break;
                    }
                }
            } 
        }
    }
    return {cost,edge};
}

class UnionFind{
    private:
    vector<int> par,siz;
    public:
    UnionFind(int N){
        par.resize(N,-1);
        siz.resize(N,1);
    }
 
    int root(int x){ //連結成分の代表頂点を返す.
        if(par.at(x) == -1) return x;
        else return par.at(x) = root(par.at(x));
    }
    bool unite(int u, int v){ //u,vを連結する 連結してた->false,した->trueを返す.
        u = root(u),v = root(v);
        if(u == v) return false;
 
        if(siz.at(u) < siz.at(v)) swap(u,v); //Union by size.
        par.at(v) = u;
        siz.at(u) += siz.at(v);
        return true;
    }
    bool issame(int u, int v){ //同じ連結成分ならtrue.
        if(root(u) == root(v)) return true;
        else return false;
    }
    int size(int pos){return siz.at(root(pos));} //posの連結成分の大きさを返す.
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N,M,T; cin >> N >> M >> T;
    vector<vector<pair<int,long long>>> Graph(N);
    vector<tuple<int,int,int>> edge;
    for(int i=0; i<M; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        int w; cin >> w;
        edge.push_back({w,u,v});
        Graph.at(u).push_back({v,w});
        Graph.at(v).push_back({u,w});
    }
    vector<int> X(T);
    for(auto &x : X) cin >> x,x--;

    if(T <= 15) cout << SteinerTree(Graph,X).first << endl;
    else{
        vector<bool> isX(N);
        for(auto x : X) isX.at(x) = true;

        vector<int> Y;
        for(int i=0; i<N; i++) if(isX.at(i) == false) Y.push_back(i);
        int n = Y.size(),n2 = 1<<n,answer = 1001001001;
        sort(edge.begin(),edge.end());
        for(int s=0; s<n2; s++){
            UnionFind Z(N);
            int siz = T,now = 0;
            for(int i=0; i<n; i++)if(s&(1<<i)) isX.at(Y.at(i)) = true,siz++;
            for(auto [w,u,v] : edge){
                if(isX.at(u) && isX.at(v) && Z.issame(u,v) == false) now += w,Z.unite(u,v);
            }

            if(Z.size(X.at(0)) == siz) answer = min(answer,now);
            for(int i=0; i<n; i++)if(s&(1<<i)) isX.at(Y.at(i)) = false;
        }
        cout << answer << endl;
    }
}
0