ソースコード
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<list>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
#define MK make_pair
const ll E=1e18+7;
const ll MOD=1000000007;
int main(){
ll n;
cin>>n;
vector<ll> dp(1<<18,E);
vector<ll> alg;
for(int i=0;i<n;i++){
ll b;
cin>>b;
alg.push_back(b);
}
vector<vector<ll>> a(n,vector<ll>(n,0));
for(int i=0;i<n;i++){
for(int t=0;t<n;t++){
cin>>a[i][t];
}
}
queue<ll> q;
for(int i=0;i<n;i++){
dp[1<<i]=alg[i];
q.push(1<<i);
}
vector<bool> done(1<<18,false);
while(!q.empty()){
ll w=q.front();
q.pop();
if(done[w]){continue;}
done[w]=true;
vector<ll> time=alg;
for(int i=0;i<n;i++){
if(w>>i&1){
for(int t=0;t<n;t++){
time[t]-=a[i][t];
}
}
}
for(int i=0;i<n;i++){
if(w&(1<<i)){continue;}
ll to=w;
to+=1<<i;
q.push(to);
dp[to]=min(dp[to],dp[w]+time[i]);
}
}
ll ans=0;
for(int i=0;i<n;i++){
ans+=1<<i;
}
cout<<dp[ans]<<endl;
return 0;
}