fork download 
  1. #include <bits/stdc++.h>
  2. #define Hoshimachi signed
  3. #define Suisei main
  4. using namespace std;
  5. #define int long long
  6. #define pii pair<int,int>
  7. #define tup tuple<int,int,int>
  8. const int N=1e3+5;
  9. int n,m,k;
  10. vector<pii> adj[N];
  11. int dp[(1<<10)+5][N];
  12. void steiner(){
  13.     memset(dp,0x3f,sizeof(dp));
  14.     for(int i=0; i<k; i++){
  15.         dp[(1<<i)][i]=0;
  16.     }
  17.     for(int mask=1; mask<(1<<k); mask++){
  18.         for(int sub=mask; sub>0; sub=(sub-1)&mask){
  19.             for(int i=0; i<n; i++){
  20.                 dp[mask][i]=min(dp[mask][i],dp[sub][i]+dp[mask^sub][i]);
  21.             }
  22.         }
  23.         priority_queue<pii,vector<pii>,greater<pii>> q;
  24.         for(int i=0; i<n; i++){
  25.             q.push({dp[mask][i],i});
  26.         }
  27.         while(!q.empty()){
  28.             auto [d,u]=q.top();
  29.             q.pop();
  30.             if(dp[mask][u]!=d) continue;
  31.             for(auto [v,w]:adj[u]){
  32.                 int nd=d+w;
  33.                 if(dp[mask][v]>nd){
  34.                     dp[mask][v]=nd;
  35.                     q.push({nd,v});
  36.                 }
  37.             }
  38.         }
  39.     }
  40.     int fm=0;
  41.     for(int i=0; i<k; i++){
  42.         fm|=(1<<i);
  43.     }
  44.     for(int i=k; i<n; i++){
  45.         cout<<dp[fm][i]<<'\n';
  46.     }
  47. }
  48. bool ok[N];
  49. tup e[N];
  50. inline bool getbit(int n, int k){
  51.     return (n>>k)&1;
  52. }
  53. struct Dsu{
  54.     vector<int> sz,par;
  55.     int sl;
  56.     void init(int n){
  57.         sl=n;
  58.         sz.resize(n+1,1);
  59.         par.resize(n+1,0);
  60.         for(int i=0; i<n; i++){
  61.             par[i]=i;
  62.             sz[i]=1;
  63.         }
  64.     }
  65.     int find(int x){
  66.         return (x==par[x]?x:(par[x]=find(par[x])));
  67.     }
  68.     bool unite(int u,int v){
  69.         u=find(u);
  70.         v=find(v);
  71.         if(u==v) return 0;
  72.         sl--;
  73.         if(sz[u]<sz[v]) swap(u,v);
  74.         sz[u]+=sz[v];
  75.         par[v]=u;
  76.         return 1;
  77.     }
  78. };
  79. Dsu dsu;
  80. void krus(){
  81.     vector<tup> all;
  82.     for(int i=1; i<=m; i++){
  83.         auto [u,v,w]=e[i];
  84.         all.push_back({w,u,v});
  85.     }
  86.     sort(all.begin(),all.end());
  87.     for(int i=0; i<k; i++) ok[i]=1;
  88.     for(int st=k; st<n; st++){
  89.         int kq=1e18;
  90.         for(int mask=0; mask<(1<<n-k); mask++){
  91.             if(!getbit(mask,st-k)) continue;
  92.             for(int j=k; j<n; j++){
  93.                 if(getbit(mask,j-k)) ok[j]=1;
  94.                 else ok[j]=0;
  95.             }
  96.             dsu.init(n);
  97.             dsu.sl=k+__builtin_popcountll(mask);
  98.             vector<tup> edge;
  99.             for(auto [w,u,v]:all){
  100.                 if(!ok[u] or !ok[v]) continue;
  101.                 edge.push_back({w,u,v});
  102.             }
  103.             int ans=0;
  104.             for(auto [w,u,v]:edge){
  105.                 if(dsu.unite(u,v)) ans+=w;
  106.             }
  107.             if(dsu.sl==1) kq=min(kq,ans);
  108.         }
  109.         cout<<kq<<'\n';
  110.     }
  111. }
  112. Hoshimachi Suisei(){
  113.     ios_base::sync_with_stdio(0);
  114.     cin.tie(0); cout.tie(0);
  115.     // freopen(".inp", "r", stdin);
  116.     // freopen(".out", "w", stdout);
  117.     cin>>n>>m>>k;
  118.     k--;
  119.     for(int i=1; i<=m; i++){
  120.         int u,v,w;
  121.         cin>>u>>v>>w;
  122.         u--,v--;
  123.         e[i]={u,v,w};
  124.         adj[u].push_back({v,w});
  125.         adj[v].push_back({u,w});
  126.     }
  127.     if(k<=10){
  128.         steiner();
  129.     }
  130.     else{
  131.         krus();
  132.     }
  133. }
Success #stdin #stdout 0.01s 11684KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/tbSEYq
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!