結果

提出番号	2222
提出者	syawacha
言語	C++
提出日時	2019-04-05 17:11:43
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

const int inf = 1000000000;

int main(){
  int N;
  cin >> N;
  int t[N];
  for(int i=0;i<N;i++) cin >> t[i];
  int a[N][N];
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      cin >> a[i][j];
    }
  }

  int dp[1 << N];
  fill(dp,dp+(1<<N),inf);
  dp[0] = 0;
  for(int i=0;i<(1<<N);i++){
    for(int j=0;j<N;j++){
      if(!(i & (1 << j))){
        int dt = 0;
        for(int k=0;k<N;k++){
          if(i & (1 << k)){
            dt += a[k][j];
          }
        }
        dp[i + (1 << j)] = min(dp[i + (1 << j)], dp[i] + t[j] - dt);
      }
    }
  }

  cout << dp[(1 << N) - 1] << endl;
  return 0;
}