fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define lb lower_bound
  3. #define pii pair<int,int>
  4. #define fi first
  5. #define int long long
  6. #define se second
  7. #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  8. #define op freopen
  9. #define sz size
  10. #define TXT "test"
  11. #define freo if(fopen(TXT".inp","r")){op(TXT".inp","r",stdin);op(TXT".out","w",stdout);}
  12.  
  13. using namespace std;
  14. const int INF=(1e18);
  15. int n,a[50][50],dp[1<<18][20];
  16.  
  17. main()
  18. {
  19.     ios;
  20.     freo;
  21.     cin>>n;
  22.     for(int i=1;i<=n;i++)
  23.     {
  24.         for(int j=1;j<=n;j-=-1)
  25.         {
  26.             cin>>a[i][j];
  27.         }
  28.     }
  29.  
  30.     for(int i=1;i<(1<<n);i++)
  31.         for(int j=1;j<=19;j++)
  32.             dp[i][j]=INF;
  33.  
  34.     for(int i=1;i<=n;i++)
  35.         dp[1<<(i-1)][i]=0;
  36.  
  37.     for(int mask=1;mask<(1<<n);mask++)
  38.     {
  39.         for(int last=1;last<=n;last++)
  40.         {
  41.             if(!(mask&(1<<(last-1))))
  42.                 continue;
  43.             for(int next=1;next<=n;next++)
  44.             {
  45.                 if(mask&(1<<(next-1)))
  46.                     continue;
  47.                 int nextper=mask|(1<<(next-1));
  48.                 dp[nextper][next]=min(dp[nextper][next],dp[mask][last]+a[last][next]);
  49.             }
  50.         }
  51.     }
  52.     int res=INT_MAX;
  53.     for(int i=1;i<=n;i++)
  54.     {
  55.         res=min(res,dp[(1<<n)-1][i]);
  56.     }
  57.     cout<<res;
  58. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2147483647
https://ideone.com/0kxQJ4
language:
C++ (gcc 8.3)
created:
1 day 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!