← 返回题单
题单练习 状态压缩DP
← 上一题 下一题 →

A6204 | Get Everything

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有 $N$ 个上锁的宝箱，编号为 $1$ 到 $N$。

商店里出售 $M$ 把钥匙。第 $i$ 把钥匙售价为 $a_i$ 日元，可以打开 $b_i$ 个宝箱，分别是 $c_{i1}$、$c_{i2}$、...、$c_{i{b_i}}$。购买的钥匙可以重复使用任意次数。

请你求出打开所有宝箱所需的最小费用。如果无法打开所有宝箱，则输出 $-1$。

输入格式

第一行输入两个整数 $N$, $M$，分别表示宝箱的数量和钥匙的个数。

接下来输入 $2M$ 行，用连续两行描述每把钥匙：
  • 第一行包含两个整数 $a_i$ 和 $b_i$，分别表示第 $i$ 把钥匙的售价和能打开的宝箱种类数。
  • 第二行包含 $b_i$ 个整数，分别是 $c_{i1}$、$c_{i2}$、...、$c_{i{b_i}}$ ，表示第 $i$ 把钥匙能够打开的宝箱。

输出格式

请输出打开所有宝箱所需的最小费用。如果无法打开所有宝箱，则输出 $-1$。

输入输出样例

输入 #1
2 3
10 1
1
15 1
2
30 2
1 2
输出 #1
25
输入 #2
12 1
100000 1
2
输出 #2
-1
输入 #3
4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3
输出 #3
69942
C++ 编辑器
输入
输出