結果

提出番号	2202
提出者	hamuhei4869
言語	C++
提出日時	2019-02-09 00:57:17
問題名	(70)アルゴリズムのお勉強
結果	WA
点数	0%

---

テストケース

ソースコード

#include <bits/stdc++.h>
using LL = long long;
const LL MOD = 1e9+9;
using namespace std;


vector<vector<int>> dp;
vector<int> task;
vector<vector<int>> Edge;
int N;
int calc(int bit, int now){
 //   cout<<bitset<10>(bit)<<endl;
    if(bit == (1<<N)-1){
        return 0;
    }
    if(dp[bit][now] != 1e9){
        return dp[bit][now];
    }
    for(int a = 0;a < N;a++){
        if(a == now)continue;
        if(!((1<<a)&bit)){
            int totalmi = 0;
            for(int b = 0;b < N;b++){
                if(bit & (1<<b)){
                    totalmi += Edge.at(a).at(b);
                }
            }
            dp[bit][now] = min(calc(bit | (1<<a),a) + max(0,task.at(a)-totalmi),dp[bit][now]);
        }
    }
    return dp[bit][now];
}
int main(){
    cin >> N;
    for(int a = 0;a < N;a++){
        int b;cin >> b;
        task.push_back(b);
    }
    dp = vector<vector<int>>((1<<N)+1,vector<int>(N,1e9));
    for(int a = 0;a < N;a++){
        vector<int> uku;
        for(int b = 0;b < N;b++){
            int c;cin >> c;
            uku.push_back(c);
        }
        Edge.push_back(uku);
    }
    int ans = 1e9;
    for(int a = 0;a < N;a++){
        ans = min(ans, calc(0 | (1<<a),a)+task.at(a));
       // cout<<ans<<endl;
    }
    cout<<ans<<endl;
}