fork download
copy 
  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. const int N=105;
  8. int n,m,k;
  9. int dp[(1<<10)+5][N],f[(1<<10)+5];
  10. vector<pii> adj[N];
  11. inline bool getbit(int n, int k){
  12.     return (n>>k)&1;
  13. }
  14. Hoshimachi Suisei(){
  15.     ios_base::sync_with_stdio(0);
  16.     cin.tie(0); cout.tie(0);
  17.     // freopen(".inp", "r", stdin);
  18.     // freopen(".out", "w", stdout);
  19.     cin>>n>>m>>k;
  20.     for(int i=1; i<=m; i++){
  21.         int u,v,w;
  22.         cin>>u>>v>>w;
  23.         u--,v--;
  24.         adj[u].push_back({v,w});
  25.         adj[v].push_back({u,w});
  26.     }
  27.     memset(dp,0x3f,sizeof(dp));
  28.     for(int i=0; i<k; i++){
  29.         dp[(1<<i)][i]=0;
  30.     }
  31.     for(int i=n-k; i<n; i++){
  32.         dp[(1<<(i-(n-k)+k))][i]=0;
  33.     }
  34.     memset(f,0x3f,sizeof(f));
  35.     for(int mask=0; mask<(1<<2*k); mask++){
  36.         for(int sub=mask; sub>0; sub=(sub-1)&mask){
  37.             for(int i=0; i<n; i++){
  38.                 dp[mask][i]=min(dp[mask][i],dp[sub][i]+dp[mask^sub][i]);   
  39.             }
  40.         }
  41.         priority_queue<pii,vector<pii>,greater<pii>> q;
  42.         for(int i=0; i<n; i++){
  43.             q.push({dp[mask][i],i});
  44.         }
  45.         while(!q.empty()){
  46.             auto [d,u]=q.top();
  47.             q.pop();
  48.             for(auto [v,w]:adj[u]){
  49.                 int nd=d+w;
  50.                 if(dp[mask][v]>nd){
  51.                     dp[mask][v]=nd;
  52.                     q.push({nd,v});
  53.                 }
  54.             }
  55.         }
  56.     }
  57.     for(int mask=0; mask<(1<<2*k); mask++){
  58.         for(int sub=mask; sub>0; sub=(sub-1)&mask){
  59.             f[mask]=min(f[mask],f[sub]+f[mask^sub]);   
  60.         }
  61.         int cnt1=0,cnt2=0;
  62.         for(int i=0; i<k; i++){
  63.             cnt1+=getbit(mask,i);
  64.             cnt2+=getbit(mask,i+k);
  65.         }
  66.         if(cnt1==cnt2){
  67.             for(int i=0; i<n; i++){
  68.                 f[mask]=min(f[mask],dp[mask][i]);
  69.             }
  70.         }
  71.     }
  72.     if(f[(1<<2*k)-1]>1e18) cout<<"No solution";
  73.     else cout<<f[(1<<2*k)-1];
  74. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
No solution
https://ideone.com/O8AEuK
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!