ソースコード
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <typeinfo>
#include <utility>
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;
int INF = 101010;
int n;
int dp[(1<<16)+1][18];
vector<int>t(20);
vector<vector<int>>a(20, vector<int>(20, 0));
int rec(int bit,int v) {
if (dp[bit][v] != -1)return dp[bit][v];
if (bit == (1 << v))return dp[bit][v] = t[v];
int res = INF;
int prev_bit = bit & ~(1 << v);
rep(u, 0, n) {
if (!(prev_bit & (1 << u)))continue;
int temp = rec(prev_bit,u)+t[v];
rep(k, 0, n) {
if (bit&(1 << k))temp -= a[k][v];
}
if (res > temp)res = temp;
}
return dp[bit][v] = res;
}
int main() {
cin >> n;
rep(i, 0, n) {
cin >> t[i];
}
rep(i, 0, n)rep(j, 0, n)cin >> a[i][j];
int res = INF;
rep(i, 0, n) {
memset(dp, -1, sizeof(dp));
res = min(res, rec((1<<n)-1,i));
}
cout << res << endl;
return 0;
}