ソースコード
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <tuple>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cassert>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
ll llpow(ll a, ll t)
{
ll res = 1;
rep(i, t) res *= a;
return res;
}
ll inf = std::numeric_limits<ll>::max();
vector<vector<ll>> drc = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<char> mrk = {'^', 'v', '<', '>'};
// s: i個のアルゴリズムの集合
// dp[s]: i個のアルゴリズムを勉強する最短時間
// dp[s] = min(dp[s - {i}] + cst(s\{i} + {i})): 漸化式
// aij: 勉強jの前にiを勉強するとaij短くなる
int main()
{
ll n;
cin >> n;
vector<ll> ts(n);
vector<vector<ll>> as(n, vector<ll>(n));
rep(i, n)
{
cin >> ts[i];
}
rep(i, n)
{
rep(j, n)
{
cin >> as[i][j];
}
}
vector<ll> dp(1 << n, inf);
dp[0] = 0;
rep(i, 1 << n)
{
rep(j, n) // j: これから勉強するやつ
{
if (!(i >> j & 1))
{
ll sum = 0;
rep(k, n) // k: 既に勉強したやつ
{
if (i >> k & 1)
{
sum += as[k][j];
}
}
dp[i | 1 << j] = min(dp[i | 1 << j], dp[i] + ts[j] - sum);
}
}
}
cout << dp[(1 << n) - 1] << endl;
}