Submission #27600466

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

long long dp[1010][1 << 13];
int main(){

    int N, M;
    cin >> N >> M;
    vector<long long>A(M);
    vector<int>key(M, 0);
    for(int i = 0; i < M; i++){
        cin >> A[i];
        int b;
        cin >> b;
        for(int j = 0; j < b; j++){
            int c;
            cin >> c;
            c--;
            key[i] |= 1 << c;
        }
    }

    for(int i = 0; i <= M; i++){
        for(int j = 0; j <= (1 << N); j++){
            dp[i][j] = 1e18;
        }
    }
    for(int i = 0; i <= M; i++) dp[i][0] = 0;


    for(int i = 0; i < M; i++){
        for(int bit = 0; bit < (1 << N); bit++){
            dp[i + 1][bit] = min(dp[i + 1][bit], dp[i][bit]);
            dp[i + 1][bit | key[i]] = min(dp[i + 1][bit | key[i]], dp[i][bit] + A[i]);
        }
    }

    if(dp[M][(1 << N) - 1] == 1e18) cout << -1 << endl;
    else cout << dp[M][(1 << N) - 1] << endl;
    return 0;
}

Submission Info

Judge Result