ソースコード
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
int main(void) {
int n;
cin >> n;
vector<int> t(n);
vector<vector<int>> d(n, vector<int>(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 >> d[i][j];
int inf = 1<<30;
vector<int> dp(1<<n, inf);
for(int i = 0; i < n; i++) dp[1<<i] = t[i];
dp[0] = 0;
for(int bit = 0; bit < (1<<n); bit++) {
for(int u = 0; u < n; u++) {
if((bit>>u)&1) continue;
int sum = 0;
for(int v = 0; v < n; v++) if((bit>>v)&1) {
sum += d[v][u];
}
int cost = t[u] - sum;
chmin(dp[bit|(1<<u)], dp[bit]+cost);
}
}
cout << dp[(1<<n)-1] << endl;
}