数据结构基础

【题目描述】网络巡视（net）BSOJ 1116

通信公司的网络各结点构成了一棵树，为了防止破坏，需要在一些结点安置巡视岗，安置巡视岗的结点可以看到相邻结点的情况。但不同的结点安置巡视岗的花费代价不同，问如何在保证全部结点安全的情况下花费的代价最小。

【输入格式】

输入数据表示一棵树，描述如下：

第1行一个整数n，表示树中结点的数目。

第2行至第n＋1行，每行描述每个结点信息，依次为：该结点标号i（0＜i≤n），在该结点安置巡视岗所需的经费k，该结点的儿子数m，接下来m个数，分别是这个结点的m个儿子的标号r₁，r₂，…，r_m。

对于一个n个结点的树，结点标号在1到n之间，且标号不重复。

【输出格式】

输出仅包含一个数，为所求的最少的代价数。

【输入样例】

6

1 30 3 2 3 4

2 16 2 5 6

3 5 0

4 4 0

5 11 0

6 5 0

【输出样例】

25

【样例说明】

样例如图4.61所示，巡视岗设置结点为2，3，4。