A7579. [ABC142E] Get Everything
编程题
普及+/提高
知识点
题目描述
有 $N$ 个上锁的宝箱，编号为 $1$ 到 $N$。
商店里出售 $M$ 把钥匙。第 $i$ 把钥匙售价为 $a_i$ 日元，可以打开 $b_i$ 种宝箱，分别是 $c_{i1}$、$c_{i2}$、...、$c_{i{b_i}}$。购买的钥匙可以重复使用任意次数。
请你求出打开所有宝箱所需的最小费用。如果无法打开所有宝箱，则输出 $-1$。
商店里出售 $M$ 把钥匙。第 $i$ 把钥匙售价为 $a_i$ 日元，可以打开 $b_i$ 种宝箱，分别是 $c_{i1}$、$c_{i2}$、...、$c_{i{b_i}}$。购买的钥匙可以重复使用任意次数。
请你求出打开所有宝箱所需的最小费用。如果无法打开所有宝箱，则输出 $-1$。
输入格式
输入以如下格式从标准输入读入：
> $N$ $M$
> $a_1$ $b_1$ $c_{11}$ $c_{12}$ ... $c_{1{b_1}}$
> $a_2$ $b_2$ $c_{21}$ $c_{22}$ ... $c_{2{b_2}}$
> $\vdots$
> $a_M$ $b_M$ $c_{M1}$ $c_{M2}$ ... $c_{M{b_M}}$
> $N$ $M$
> $a_1$ $b_1$ $c_{11}$ $c_{12}$ ... $c_{1{b_1}}$
> $a_2$ $b_2$ $c_{21}$ $c_{22}$ ... $c_{2{b_2}}$
> $\vdots$
> $a_M$ $b_M$ $c_{M1}$ $c_{M2}$ ... $c_{M{b_M}}$
输出格式
请输出打开所有宝箱所需的最小费用。如果无法打开所有宝箱，则输出 $-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
说明/提示
### 限制条件
- 所有输入均为整数。
- $1 \leq N \leq 12$
- $1 \leq M \leq 10^3$
- $1 \leq a_i \leq 10^5$
- $1 \leq b_i \leq N$
- $1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N$
### 样例解释 1
如果购买钥匙 $1$ 和钥匙 $2$，可以打开所有宝箱，此时总费用为 $25$ 日元，这是最小值。
### 样例解释 2
无法打开所有宝箱。
- 所有输入均为整数。
- $1 \leq N \leq 12$
- $1 \leq M \leq 10^3$
- $1 \leq a_i \leq 10^5$
- $1 \leq b_i \leq N$
- $1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N$
### 样例解释 1
如果购买钥匙 $1$ 和钥匙 $2$，可以打开所有宝箱，此时总费用为 $25$ 日元，这是最小值。
### 样例解释 2
无法打开所有宝箱。