結果

提出番号	2442
提出者	keko33
言語	C++
提出日時	2023-05-13 16:47:21
問題名	(70)アルゴリズムのお勉強
結果	WA
点数	0%

---

テストケース

ソースコード

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

#define rep(i, h) for(int i = 0; i < (h); ++i)
#define reps(i, s, h) for(int i = (s); i < (h); ++i)
#define rrep(i, s, h) for(int i = (s); i >= (h); --i)
#define vi vector<int>
#define vl vector<ll>
#define pl pair<ll, ll>
#define all(v) (v).begin(), (v).end()

template <class T> void chmin(T &v, T b) {
    if(v > b)
        v = b;
}
template <class T> void chmax(T &v, T b) {
    if(v < b)
        v = b;
}

const ll inf = LONG_LONG_MAX / 2;
const int mod = 1e9 + 7;
const int MAX = 1e6 + 5;

ll n;
ll dc[20][20];
ll dp[MAX][20];
ll t[20];

string bitDisp(ll n) {
    bitset<8> bs(n);
    return bs.to_string();
}

ll rec(ll s, ll cur) {

    string str = bitDisp(s);

    if(s == 0) {
        if(cur == 0) {
            return 0;
        } else {
            return inf;
        }
    }

    if((s & (1 << cur)) == 0) {
        return inf;
    }

    ll &ret = dp[s][cur];
    if(ret != 0)
        return ret;

    ret = inf;
    rep(nx, n) {
        ll rtn = rec(s ^ (1 << cur), nx) + t[cur] - dc[cur][nx];
        ret = min(ret, rtn);
    }
    return ret;
}

int main() {

    cin >> n;

    rep(i, n) cin >> t[i];

    rep(i, n) {
        rep(j, n) { cin >> dc[i][j]; }
    }

    ll ans = rec((1 << n) - 1, 0);

    cout << ans << endl;

    return 0;
}