結果

提出番号	2452
提出者	aiueo
言語	C++
提出日時	2026-03-13 22:43:59
問題名	(70)アルゴリズムのお勉強
結果	WJ
点数	0%

---

テストケース

ソースコード

#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}

int main(void) {
    int n;
    cin >> n;

    vector<int> t(n);
    vector<vector<int>> d(n, vector<int>(n));

    for(int i = 0; i < n; i++) cin >> t[i];
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> d[i][j];

    int inf = 1<<30;
    vector<int> dp(1<<n, inf);
    for(int i = 0; i < n; i++) dp[1<<i] = t[i];
    dp[0] = 0;

    for(int bit = 0; bit < (1<<n); bit++) {
        for(int u = 0; u < n; u++) {
            if((bit>>u)&1) continue;

            int sum = 0;
            for(int v = 0; v < n; v++) if((bit>>v)&1) {
                sum += d[v][u];
            }

            int cost = t[u] - sum;
            chmin(dp[bit|(1<<u)], dp[bit]+cost);
        }
    }

    cout << dp[(1<<n)-1] << endl;
}