fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3. const int INF = 1e9 ;
  4. const int N = 30 ;
  5. int n ;
  6. int c[N][N] ;
  7. bool visited[N] ;
  8. int choose[N] ;
  9. int ans[N] ;
  10. int minc =INF ;
  11. int curc = 0 ;
  12. int min_edge[N] ;
  13. int total_min_edge = 0 ;
  14. void dq ( int id ){
  15.     int lb = curc + total_min_edge ;
  16.     if ( lb >= minc )
  17.         return ;
  18.     for ( int j = 2 ; j <= n ; j++ ){
  19.         if ( !visited[j] ){
  20.             if (curc + c[choose[id - 1]][j] + (total_min_edge - min_edge[choose[id - 1]]) < minc ) {
  21.                 choose[id] = j ;
  22.                 visited[j] = true ;
  23.                 curc += c[choose[id-1]][j] ;
  24.                 total_min_edge -= min_edge[choose[id-1]] ;
  25.                 if ( id == n ){
  26.                     if ( curc + c[choose[n]][1] < minc ){
  27.                         minc = curc + c[choose[n]][1] ;
  28.                         for ( int i = 1 ; i <= n ; i++ )
  29.                             ans[i] = choose[i] ;
  30.                     }
  31.                 }
  32.                 else{
  33.                     dq( id + 1 ) ;
  34.                 }
  35.                 total_min_edge += min_edge[choose[id - 1]];
  36.                 curc -= c[choose[id - 1]][j];
  37.                 visited[j] = false;
  38.             }
  39.         }
  40.     }
  41. }
  42. int main(){
  43.     cin >> n ;
  44.     for ( int i = 1 ; i <= n ; i++ ){
  45.         min_edge[i] = INF ;
  46.         for ( int j = 1 ; j <= n ; j++ ){
  47.             cin >> c[i][j] ;
  48.             if ( j != i && c[i][j] < min_edge[i] )
  49.                 min_edge[i] = c[i][j] ;
  50.         }
  51.         total_min_edge += min_edge[i] ;
  52.     }
  53.     choose[1] = 1 ;
  54.     visited[1] = true ;
  55.     dq(2) ;
  56.     cout << minc << endl ;
  57.     for ( int i = 1 ; i <= n ; i++ )
  58.         cout << ans[i] << " " ;
  59. }
  60.  
  61.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000
https://ideone.com/wGqWmc
language:
C++14 (gcc 8.3)
created:
6 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!