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

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

    输入格式

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

    输出格式

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

    样例输入

    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

    样例输出

    216