結果

提出番号	1697
提出者	popo
言語	C++
提出日時	2018-08-04 13:32:18
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;

int dp[1<<16][16];
int n,t[55],a[55][55];

int main(){
  cin>>n;
  r(i,n)cin>>t[i];
  r(i,n)r(j,n)cin>>a[i][j];
  r(i,1<<16)r(j,16)dp[i][j]=1e9;
  dp[0][0]=0;
  for(int i=0;i<(1<<n);i++){
    for(int j=0;j<n;j++){
      if(dp[i][j]==1e9)continue;
      for(int k=0;k<n;k++){
        if(i&(1<<k))continue;
        int s=t[k];
        r(l,n)if(i&(1<<l))s-=a[l][k];
        dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+s);
      }
    }
  }
  int ans=1e9;
  r(i,n)ans=min(ans,dp[(1<<n)-1][i]);
  cout<<ans<<endl;
}