算法
(bitDP) $O(2^N \cdot M)$
注意到 $N$ 的数据范围很小,所以我们可以先考虑 bitDP
记 dp[i][S]
表示选取前 $i$ 把钥匙中的一些钥匙可以打开集合 $S$ 中的所有宝箱的最小费用
转移方程:
若 $T = S$ 与第 $i$ 把钥匙所能打开宝箱集合的并集, 则
$$ dp[i][T] = \min(dp[i][T], dp[i-1][S] + \text{第}i\text{把钥匙的费用}) $$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using P = std::pair<int, int>;
inline void chmin(int &x, int y) { if (x > y) x = y; }
int main() {
int n, m;
cin >> n >> m;
vector<P> key;
rep(i, m) {
int a, b;
cin >> a >> b;
int s = 0;
rep(j, b) {
int c;
cin >> c;
--c;
s |= 1<<c;
}
key.emplace_back(s, a);
}
const int INF = 1001001001;
vector<int> dp(1<<n, INF);
dp[0] = 0;
rep(s, 1<<n) {
rep(i, m) {
int t = s | key[i].first;
int cost = dp[s] + key[i].second;
chmin(dp[t], cost);
}
}
int ans = dp.back();
if (ans == INF) ans = -1;
cout << ans << '\n';
return 0;
}