T24:Get Everything

1）题目意思

有 N 个宝箱（1..N），有 M 把钥匙。第 i 把钥匙价格 ai，能打开一组宝箱（给出列表）。你可以买任意多把钥匙（每把最多买一次即可，买了能重复使用，不需要买多次）。

目标：用买到的钥匙覆盖所有宝箱（每个宝箱至少能被某把已买钥匙打开），求最小总费用；如果做不到输出 -1。

范围：N<=12，M<=1000，适合状态压缩 DP。

---

2）思路解析（状态压缩最短路 / 0-1选择DP）

用二进制 mask 表示已经能打开的宝箱集合：

• mask 的第 j 位为 1，表示宝箱 j+1 已经能打开
• 目标 FULL = (1<<N)-1

把每把钥匙转成一个 keyMask（它能打开哪些宝箱的集合）。

定义：

• dp[mask]：达到集合 mask 的最小费用

初始化：

• dp[0]=0，其它为无穷大

转移：

• 枚举每一把钥匙 keyMask 和费用 a
• 对所有 mask：
  • nmask = mask | keyMask
  • dp[nmask] = min(dp[nmask], dp[mask] + a)

因为每把钥匙买不买是 0/1（买一次足够），所以这是典型的 0/1 背包式转移；为了不让同一把钥匙被重复使用，枚举 mask 时用任意顺序都可以（这里用全量枚举 + 使用 ndp 或者倒序都行）。我用更稳的 ndp 写法，避免顺序讨论。

答案：

• 若 dp[FULL] 仍是无穷大，输出 -1
• 否则输出 dp[FULL]

复杂度：

• 状态数最多 2^12=4096
• 转移 M * 2^N，约 1000*4096=400万，能过。

---

3）代码

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

const long long INF=(1LL<<62);                                // 定义无穷大表示不可达

int main(){                                                   // 主函数入口
    ios::sync_with_stdio(false);                              // 加速输入输出
    cin.tie(nullptr);                                         // 加速输入输出

    int N,M;                                                  // N个宝箱，M把钥匙
    cin>>N>>M;                                                // 读入N和M

    int FULL=(1<<N)-1;                                        // FULL表示所有宝箱都覆盖

    static long long dp[1<<12];                               // dp[mask]：覆盖mask的最小费用
    static long long ndp[1<<12];                              // ndp用于处理下一把钥匙后的dp

    for(int mask=0;mask<=FULL;mask++)dp[mask]=INF;            // 初始化dp为INF
    dp[0]=0;                                                  // 初始：什么都打不开，费用为0

    for(int i=1;i<=M;i++){                                    // 枚举每一把钥匙
        long long a;                                          // 钥匙价格
        int b;                                                // 该钥匙能打开的宝箱数量
        cin>>a>>b;                                            // 读入a和b

        int keyMask=0;                                        // 该钥匙能打开的宝箱集合mask
        for(int j=1;j<=b;j++){                                // 读入能打开的宝箱编号
            int c;                                            // 宝箱编号
            cin>>c;                                           // 读入宝箱编号
            c--;                                              // 转成0-based
            keyMask|=(1<<c);                                  // 把该宝箱加入集合
        }

        for(int mask=0;mask<=FULL;mask++)ndp[mask]=dp[mask];  // 先复制“不买这把钥匙”的情况

        for(int mask=0;mask<=FULL;mask++){                    // 枚举当前覆盖集合mask
            if(dp[mask]>=INF)continue;                        // 如果mask不可达则跳过
            int nmask=mask|keyMask;                           // 买这把钥匙后的新覆盖集合
            ndp[nmask]=min(ndp[nmask],dp[mask]+a);            // 尝试更新最小费用
        }

        for(int mask=0;mask<=FULL;mask++)dp[mask]=ndp[mask];  // 更新dp进入下一轮
    }

    if(dp[FULL]>=INF){                                        // 如果最终仍不可达
        cout<<-1<<endl;                                       // 输出-1
    }else{                                                    // 如果可达
        cout<<dp[FULL]<<endl;                                 // 输出最小费用
    }

    return 0;                                                 // 程序结束
}