fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,k;
  4. int a[23][23],visited[23],cmin=INT_MAX,ans=INT_MAX,space=0;
  5. void backtrack(int curr,int index,int u){
  6.     if(index==2*n){
  7.         ans=min(ans,curr+a[u][0]);
  8.         return;
  9.     }
  10.     if(curr+(2*n-index+1)*cmin>=ans){
  11.         return;
  12.     }
  13.     for(int i=1;i<=2*n;i++){
  14.         if(!visited[i]){
  15.             if(i<=n){
  16.                 if(space<k){
  17.                     visited[i]=1;
  18.                     space++;
  19.                     backtrack(curr+a[u][i],index+1,i);
  20.                     visited[i]=0;
  21.                     space--;
  22.                 }else{
  23.                     continue;
  24.                 }
  25.             }else{
  26.                 if(visited[i-n]){
  27.                     space--;
  28.                     visited[i]=1;
  29.                     backtrack(curr+a[u][i],index+1,i);
  30.                     space++;
  31.                     visited[i]=0;
  32.                 }
  33.             }
  34.         }else{
  35.             continue;
  36.         }
  37.     }
  38. }
  39. int main()
  40. {
  41.     ios_base::sync_with_stdio(false);
  42.     cin.tie(NULL);
  43.     cin >> n >> k;
  44.     //visited[0]=1;
  45.     for(int i=0;i<=2*n;i++){
  46.         for(int j=0;j<=2*n;j++){
  47.             cin >> a[i][j];
  48.             if(i!=j){
  49.                 cmin=min(cmin,a[i][j]);
  50.             }
  51.         }
  52.     }
  53.     backtrack(0,0,0);
  54.     cout << ans;
  55. }
  56.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZAKsJH
language:
C++14 (gcc 8.3)
created:
2 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!