ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
vector<vector<int> > A;
int N;
vector<int> T;
vector<int> dp;
int rec(int a) {
if (dp[a] != -1)return dp[a];
int t;
dp[a] = (int)1 << 60;
for (int j = 0; j < N; j++) {
if ((a & (1 << j)) == 0) {
t = T[j];
for (int i = 0; i < N; i++) {
if ((a & (1 << i))) {
t -= A[i][j];
}
}
dp[a] = min(dp[a], rec(a | (1 << j)) + t);
}
}
return dp[a];
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N;
T.resize(N);
int res = 0;
for (int i = 0; i < N; i++) {
cin >> T[i];
}
A.resize(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> A[i][j];
}
}
dp.resize(1 << N, -1);
dp[(1 << N) - 1] = 0;
cout << rec(0) << endl;
}