ソースコード
#include <bits/stdc++.h>
#define inf 1000000000 //1E+9
#define mod 1000000007
using namespace std;
int n, t[16], a[16][16];
int dp[131072]; //dp[x]=min for making x
int func(unsigned int I){
if(dp[I]!=inf) return dp[I];
for(int i=0;i<n;i++){
if(I & (1<<i)){
for(int j=0;j<n;j++) if((I&~(1<<i))&(1<<j)) dp[I]=min(dp[I], func((I&~(1<<i)))+t[i]-a[j][i]);
}
}
return dp[I];
}
int main(){
/*
n=3; t[0]=5;t[1]=6;t[2]=7;
a[0][0]=0;a[0][1]=1;a[0][2]=2;
a[1][0]=1;a[1][1]=0;a[1][2]=1;
a[2][0]=2;a[2][1]=2;a[2][2]=0;
*/
cin>>n;
for(int i=0;i<n;i++)cin>>t[i];
for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j];
for(int i=1;i<131072;i++)dp[i]=inf;
dp[0]=0;
for(int i=0;i<n;i++)dp[int(pow(2.0,i))]=t[i];
unsigned int full=pow(2.0,n)-1;
cout<<func(full)<<endl;
/*for(int i=0;i<=n;i++){
for(int j=0;j<=full;j++){
if(bitset<5>(j).count()==i)cout<<bitset<5>(j)<<" "<<func(j)<<endl;
}}*/
return 0;
}