[MtOI2018] gcd?人生赢家!
题目背景
gcd 是一个热爱游戏的人。
题目描述
gcd 最近在玩一个有趣的游戏。
我们把这个游戏抽象成一张图,图上有 $n$ 个点,gcd 需要寻找总计 $m$ 件宝物,它们分布在图上。
对于每件宝物而言,将会有一个前置集合 $S$。只有当取得所有前置宝物时,才能获得该宝物。
gcd 拥有一件神器,这件神器具有传送功能,它可以使用 $k$ 次,可以传送到一个任意节点。
对于游戏而言,肯定会有额外的成就,这些成就会奖励一定的传送次数,成就的达成是满足集合 $S$ 的一瞬间。
现在 gcd 想知道能最快通关的方法,请你求出通关的最少时间。
输入输出格式
输入格式
输入共 $s+m+e+6$ 行。
第 $1$ 行输入 $3$ 个正整数 $n,m,k$。
第 $2$ 行输入 $1$ 个正整数 $s$ 表示成就的数量。
以下 $s$ 行每行输入 $1$ 个非负整数 $num$ 表示需求多少个宝物,然后输入 $num$ 个数,为所需宝物编号。
第 $s+3$ 行输入 $s$ 个正整数 $a_1,a_2,\cdots a_s$ 表示成就的奖励次数。
第 $s+4$ 行输入 $m$ 个正整数 $p_1,p_2,\cdots p_m$ 表示宝物的位置。
第 $s+5$ 行输入 $1$ 个正整数 $e$ 表示边的总数。
以下 $e$ 行每行输入 $3$ 个正整数 $x,y,z$ 表示 $x$ 与 $y$ 之间有一条边权为 $z$ 的无向边连接。
以下 $m$ 行每行输入 $1$ 个非负整数 $num$ 表示宝物前置要求个数,然后输入 $num$ 个数,为要求的编号。
最后一行输入 $1$ 个正整数 $st$ 表示起点。
输出格式
输出共 $1$ 行 $1$ 个正整数,输出最少时间。
输入输出样例
输入样例 #1
3 2 0
1
1 1
1
2 3
3
1 2 20
1 3 20
3 2 1
0
0
1
输出样例 #1
20
输入样例 #2
3 2 0
1
1 1
1
2 3
3
1 2 1
1 3 20
3 2 20
1 2
0
1
输出样例 #2
40
说明
### 子任务
对于 $20\%$ 的数据,$s=0$。
对于 $100\%$ 的数据,$n\leq 200$,$m\leq 12$,$k\leq 4$,$s\leq 8$,$e\leq 20000$ ,奖励次数总和不超过 $8$,保证每两个宝物的位置不相同,可能有重边,保证有解。
### 题目来源
[MtOI2018 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T5
出题人:b2019dy
78488