TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1228
  • Problem
  • P1228丛林道路
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    热带小岛“拉格瑞珊”的酋长面临着一个问题:很久以前,通过大量外来资金援助,在岛上的村庄之间修建了很多道路。但是由于岛上的丛林生长得特别快,掩盖了很多公路,而如此庞大的公路网络维护起来费用就相当昂贵。小岛的管理委员会必须选择停止某些公路的维护工作。下面左边的地图显示了现在正在使用的道路和每条道路每个月需花费的维护费用。酋长要告诉委员会只保留哪些公路便可连接岛上的所有村庄并且使得每个月的维护费用总和最少。下面右边的地图便是最便宜的公路连接方案。你的任务就是写一个程序来解决这个问题。

    Input Format

    第一行,一个数字n(1<n<27)表示村庄的个数。
    接下来n-1按字母表顺序排列。每行开头是一个大写字母,表示村庄的编号。接着是一个数字k,表示连接该村庄的公路数量。如果公路条数k不为0,则后面是和该村庄直接相连的k个村庄的编号(按字母表顺序排列)和维护连接这两个村庄的公路的花费。
    注:每个村庄最多有15条公路和其他村庄直接相连,每条公路的维护费用不超过75,公路的总条数不超过100

    Output Format

    只有一行:连接所有村庄的公路的最小维护费用。

    Sample Input

    9
    A 2 B 12 I 25
    B 3 C 10 H 40 I 8
    C 2 D 18 G 55
    D 1 E 44
    E 2 F 60 G 38
    F 0
    G 1 H 35
    H 1 I 35

    Sample Output

    216