Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

#21614. 【PR #1】守卫

Statistics

在 P 国有 $n$ 个村子,以及 $m$ 条待修建的双向公路,第 $i$ 条公路连接 $u_i$ 和 $v_i$,修建的代价为 $w_i$。

国王找到了 $k$ 个守卫,每个守卫将入驻一个村子,第 $i$ 个守卫能入驻的村子是集合 $S_i$。

国王将派遣每个守卫去一个村子,并修建一些公路。

国王希望整个国家得到保护的同时,尽可能节省开支。因此他希望每个村子可以被恰好一个守卫经过若干条公路到达。

国王想要知道,是否存在一种修建公路和派遣守卫的方案,如果存在,修建公路的代价之和最小是多少。

输入格式

第一行三个整数 $n,m,k$,表示村子个数,公路条数和守卫个数。

接下来 $m$ 行每行三个整数 $u_i, v_i, w_i$ 描述了一条公路。

接下来 $k$ 行,每行 $|S_i|+1$ 个整数,第一个整数 $|S_i|$ 表示集合大小,接下来 $|S_i|$ 个整数 $s_{i,j}$ 表示集合内容。

输出格式

一行一个整数,如果存在方案输出最小的代价之和,否则输出 -1

样例一

input

5 6 2
1 2 1
1 3 4
2 4 2
2 5 5
3 4 7
4 5 3
2 1 2
2 2 4

output

8

explanation

修建第 $1,2,6$ 条道路,两个守卫分别入驻 $1,4$ 号村子。

样例二

见下发文件。

数据范围与提示

本题共 $20$ 组测试点,各 $5$ 分。

对于所有数据,$1\leq n\leq 300$,$0\leq m\leq \frac{n(n-1)}{2}$,$1\leq k\leq n$,$1\leq w_i\leq 1000$。

对于所有数据,保证 $1\leq u_i\lt v_i\leq n$,$1\leq |S_i|\leq n$,$1\leq s_{i,j}\leq n$,$\forall i\neq j, (u_i,v_i)\neq (u_j, v_j)$,$\forall x,i\neq j, s_{x,i}\neq s_{x,j}$。

测试点编号 特殊性质
$1\sim 2$ $n\le 6$
$3\sim 4$ $S_i$ 的大小均为 $1$
$5\sim 9$ $w_i=1$
$10\sim 14$ 公路不可能修建出环
$15\sim 20$ $ $

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$