結果

提出番号	1911
提出者	Gacho_0716
言語	C++
提出日時	2018-08-04 14:31:28
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 1e9;

int N, t[16], a[16][16];
int dp[1<<16];

signed main(){
  
  cin>>N;
  
  int tsum = 0;
  
  for(int i=0;i<N;i++){
    cin>>t[i];
    tsum += t[i];
  }
  
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++) cin>>a[i][j];
  
  for(int i=0;i<(1<<N);i++) dp[i] = INF;
  
  for(int i=0;i<N;i++) dp[1<<i] = tsum;
  
  for(int i=0;i<(1<<N);i++){
    
    if( dp[i] == INF ) continue;
      
    for(int j=0;j<N;j++){
	
      if( i >> j & 1 ) continue;
	
      int S = 0;
	
      for(int k=0;k<N;k++){
	if( i >> k & 1 ) S += a[k][j];
      }
	
      dp[i|(1<<j)] = min( dp[i|(1<<j)], dp[i] - S );
	
    }
      
  }
  
  cout<<dp[(1<<N)-1]<<endl;
  
  return 0;
}