#810806 (C++17) No.114 遠い未来

• 問題: No.114 遠い未来
• ユーザー: tko919
• 提出日時: 2022-10-25 04:15:59
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,450 ms / 5,000 ms
• コード長: 7,787 bytes
• コンパイル時間: 2,621 ms
• コンパイル使用メモリ: 221,000 KB
• 最終ジャッジ日時: 2025-02-08 12:31:09
• ジャッジサーバーID （参考情報）: judge3 / judge3

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

ソースコード

#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
using ll=long long int;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
#line 2 "library/Utility/fastio.hpp"
#include <unistd.h>

class FastIO{
    static constexpr int L=1<<16;
    char rdbuf[L];
    int rdLeft=0,rdRight=0;
    inline void reload(){
        int len=rdRight-rdLeft;
        memmove(rdbuf,rdbuf+rdLeft,len);
        rdLeft=0,rdRight=len;
        rdRight+=fread(rdbuf+len,1,L-len,stdin);
    }
    inline bool skip(){
        for(;;){
            while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;
            if(rdLeft==rdRight){
                reload();
                if(rdLeft==rdRight)return false;
            }
            else break;
        }
        return true;
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        if(rdbuf[rdLeft]!='.')return true;
        rdLeft++;
        T base=.1;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x+=base*(rdbuf[rdLeft++]^48);
            base*=.1;
        }
        if(neg)x=-x;
        return true;
    }
    inline bool _read(char& x){
        if(!skip())return false;
        if(rdLeft+1>=rdRight)reload();
        x=rdbuf[rdLeft++];
        return true;
    }
    inline bool _read(string& x){
        if(!skip())return false;
        for(;;){
            int pos=rdLeft;
            while(pos<rdRight and rdbuf[pos]>' ')pos++;
            x.append(rdbuf+rdLeft,pos-rdLeft);
            if(rdLeft==pos)break;
            rdLeft=pos;
            if(rdLeft==rdRight)reload();
            else break;
        }
        return true;
    }
    template<typename T>inline bool _read(vector<T>& v){
        for(auto& x:v){
            if(!_read(x))return false;
        }
        return true;
    }

    char wtbuf[L],tmp[50];
    int wtRight=0;
    inline void flush(){
        fwrite(wtbuf,1,wtRight,stdout);
        wtRight=0;
    }
    inline void _write(const char& x){
        if(wtRight>L-32)flush();
        wtbuf[wtRight++]=x;
    }
    inline void _write(const string& x){
        for(auto& c:x)_write(c);
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){
        if(wtRight>L-32)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {
                switch (sizeof(x)) {
                case 2: _write("32768"); return;
                case 4: _write("2147483648"); return;
                case 8: _write("9223372036854775808"); return;
                }
            }
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    template<typename T>inline void _write(const vector<T>& v){
        rep(i,0,v.size()){
            if(i)_write(' ');
            _write(v[i]);
        }
    }
public:
    FastIO(){}
    ~FastIO(){flush();}
    inline void read(){}
    template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){
        assert(_read(head));
        read(tail...); 
    }
    template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}
    template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){
        if(space)_write(' ');
        _write(head);
        write<ln,true>(tail...); 
    }
};

/**
 * @brief Fast IO
 */
#line 3 "sol.cpp"

struct SteinerTree{
    using P=pair<ll,ll>;
    int n;
    vector<vector<P>> g;
    SteinerTree(int _n):n(_n),g(n){}
    void add_edge(int u,int v,ll c){
        g[u].push_back({v,c});
        g[v].push_back({u,c});
    }
    ll run(vector<int>& term){
        int k=term.size();
        if(k<=1)return 0;
        vector dp(1<<k,vector<ll>(n,INF));
        rep(i,0,k)dp[1<<i][term[i]]=0;
        using P=pair<ll,int>;
        rep(mask,1,1<<k){
            for(ll sub=mask;;sub=(sub-1)&mask){
                rep(v,0,n)chmin(dp[mask][v],dp[sub][v]+dp[mask^sub][v]);
                if(sub==0)break;
            }
            priority_queue<P,vector<P>,greater<P>> pq;
            rep(v,0,n)pq.push({dp[mask][v],v});
            while(!pq.empty()){
                auto [d,v]=pq.top();
                pq.pop();
                if(dp[mask][v]<d)continue;
                for(auto& [nxt,c]:g[v])if(chmin(dp[mask][nxt],d+c)){
                    pq.push({dp[mask][nxt],nxt});
                }
            }
        }
        ll ret=INF;
        rep(j,0,n)chmin(ret,dp[(1<<k)-1][j]);
        return ret;
    }
};

#line 2 "library/DataStructure/unionfind.hpp"

struct UnionFind{
    vector<int> par; int n;
    UnionFind(){}
    UnionFind(int _n):par(_n,-1),n(_n){}
    int root(int x){return par[x]<0?x:par[x]=root(par[x]);}
    bool same(int x,int y){return root(x)==root(y);}
    int size(int x){return -par[root(x)];}
    bool unite(int x,int y){
        x=root(x),y=root(y); if(x==y)return false;
        if(size(x)>size(y))swap(x,y);
        par[y]+=par[x]; par[x]=y; n--; return true;
    }
};

/**
 * @brief Union Find
 */
#line 42 "sol.cpp"

FastIO io;
int main(){
    int n,m,t;
    io.read(n,m,t);
    if(t<=15){
        SteinerTree buf(n);
        rep(i,0,m){
            int a,b,c;
            io.read(a,b,c);
            a--; b--;
            buf.add_edge(a,b,c);
        }
        vector<int> vs(t);
        io.read(vs);
        for(auto& v:vs)v--;
        ll ret=buf.run(vs);
        io.write(ret);
    }
    else{
        using P=pair<int,int>;
        using T=pair<int,P>;
        vector<T> es;
        rep(i,0,m){
            int a,b,c;
            io.read(a,b,c);
            a--; b--;
            es.push_back({c,{a,b}});
        }
        sort(ALL(es));
        vector<int> vs(t);
        io.read(vs);
        for(auto& v:vs)v--;
        int ret=inf;
        auto process=[&](ll mask){
            int x=__builtin_popcountll(mask);
            UnionFind uni(n);
            int sub=0;
            for(auto& [c,uv]:es){
                auto [u,v]=uv;
                if(mask>>u&1 and mask>>v&1){
                    if(uni.unite(u,v)){
                        x--;
                        sub+=c;
                    }
                }
            }
            if(x==1)chmin(ret,sub);
        };
        ll used=0;
        rep(i,0,t)used|=1LL<<vs[i];
        ll rem=(1LL<<n)-1-used;
        for(ll sub=rem;;sub=(sub-1)&rem){
            process(sub|used);
            if(sub==0)break;
        }
        io.write(ret);
    }
    return 0;
}