TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2306
  • 問題
  • P2306警卫安排
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    一个重要的基地被分为n个连通的区域。出于某种神秘的原因,这些区域以一个区域为核心,呈一颗树形分布。
      在每个区域安排警卫所需要的费用是不同的,而每个区域的警卫都可以望见其相邻的区域,只要一个区域被一个警卫望见或者是安排有警卫,这个区域就是安全的。你的任务是:在确保所有区域都是安全的情况下,找到安排警卫的最小费用。


    入力形式

    第一行n,表示树中结点的数目。
    接下来的n行描述了n个区域的信息,每一行包含的整数依次为:区域的标号i(0<i<=n),在区域i安排警卫的费用k,区域i的子结点数目m,接下来m个数为区域i的子结点编号。

    出力形式

    一行一个整数,为最小的安排费用。

    サンプル入力 1

    6
    1 30 3 2 3 4
    2 16 2 5 6
    3 5 0
    4 4 0
    5 11 0
    6 5 0

    サンプル出力 1

    25

    サンプル入力 2

    10
    5 23 1 8 
    8 61 2 1 3 
    1 37 1 9 
    9 20 1 10 
    10 18 0 
    3 24 2 6 7 
    6 94 1 4 
    4 98 1 2 
    2 92 0 
    7 40 0 

    サンプル出力 2

    159

    ヒント

    0<n<=720。