TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1286
  • 题目
  • P1286小胖守皇宫
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    小胖成了皇上特聘的御前一品侍卫。
    皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状;某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。
    可是小胖手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。
    帮助小胖布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。

    输入格式

    输入文件中数据表示一棵树,描述如下:
    第1行 n,表示树中结点的数目。
    第2行至第n+1行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号i(0<i<=n),在该宫殿安置侍卫所需的经费k,该边的儿子数m,接下来m个数,分别是这个节点的m个儿子的标号r1,r2,...,rm。
    对于一个n(0 < n <= 1500)个结点的树,结点标号在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

    提示

    如图