結果

提出番号	2427
提出者	Focus_Sash
言語	C++
提出日時	2021-04-27 19:04:31
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define V vector
const ll INF = 1000000000000000001;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    ll n; cin >> n;
    vl t(n); rep(i,n) cin >> t[i];
    V<vl> a(n, vl(n));
    rep(i,n) rep(j,n) cin >> a[i][j];

    vl dp(1<<n, INF);
    dp[0] = 0;
    rep(S, 1<<n){
        rep(i, n){
            if(S & (1<<i)) continue;
            ll red = 0;
            rep(j,n){
                if(S & (1<<j)) red += a[j][i];
            }
            dp[S|(1<<i)] = min(dp[S|(1<<i)], dp[S] + t[i] - red);
        }
    }
    cout << dp[(1<<n)-1] << '\n';

    return 0;
}