丛林中的路

热带岛屿Lagrishan的首领现在面临一个问题：几年前，一批外援资金被用于维护村落之间的道路，但日益繁茂的丛林无情的侵蚀着村民的道路，导致道路维修开销巨大，长老会不得不放弃部分道路的维护。上图左侧图显示的是正在使用道路的简图以及每条路每个月的维修费用（单位为aacms）。现在长老会需要提出一种方案，即需要保证村落之间都可以互相到达，又要将每个月的道路维修费用控制在最小。村子编号为从A到I。上图右侧显示的方案最小维修开销为216 aacms每月。

输入包含1~100个数据集，最后一行为0.每个数据集第一行为村落数目n, 1 < n < 27,依次用字母表的前n个字母标记。接下来有n-1行，每行的第一个数据便是按字母顺序排列的村子编号（不包括最后一个村庄）。每个村庄后面的数据k代表该村庄通往编号在其之后的村庄的道路数目，如A 2 B 12 I 25，代表A村庄有2个编号在A之后的村庄和其相连。若k大于0，k后面会依次给出这k个村庄的编号以及各自到起始村庄的道路维修费用，如A 2 B 12 I 25，代表A和B之间道路维修费用为12， A和I之间道路维修费用为25（维修费用为不超过100的正整数）.路的总数目不超过75条，每个村庄到其他村庄不会有超过15条路（包括编号在其之前和之后的）。

每个数据集有一个输出：针对解决方案每个月维修道路的小费用。
提示：蛮力算法虽能找出解决方案，但将会超出时间限制。

9
A 2 B 12 I 25

相关文章：

ROADS

Heavy Transportation

八进制小数

矩形分割

删除数组中的元素（链表）

统计学生信息

【BZOJ 1588】营业额统计 【HNOI2002】【平衡树】【双向链表】

[Latex学习笔记]数学公式基本命令

一些思考

【BZOJ 1192】[HNOI2006]鬼谷子的钱袋

【BZOJ 1800】[Ahoi2009]fly 飞行棋

【BZOJ 2761】[JLOI2011]不重复数字

【HDU 1599】find the mincost route 【最小环】

【HDU 2833】WuKong 【Floyd】

【NOIP2015】跳石头 【二分答案】

网络传输文件的问题

[ JavaScript ] 数据结构与算法 —— 链表

Android 架构优化~MVP 架构改造

Android组件 - 收藏集 - 掘金

Bytom交易说明（账户管理模式）

Docker容器管理

ES6系列（二）变量的解构赋值

Linux Process Manage

MySQL的数据类型

Nginx 通过 Lua + Redis 实现动态封禁 IP

PAT A1050

SegmentFault 社区上线小程序开发频道，助力小程序开发者生态

Spring Boot快速入门（一）：Hello Spring Boot

vue.js框架原理浅析

Windows Containers 大冒险: 容器网络

翻译：Hystrix - How To Use

解决jsp引用其他项目时出现的 cannot be resolved to a type错误

让你成为前端，后端或全栈开发程序员的进阶指南，一门学到老的技术

通过来模仿稀土掘金个人页面的布局来学习使用CoordinatorLayout

最简单的无缝轮播

# 计算机视觉入门

#{}和${}的区别？

#define 用法

（day 2）JavaScript学习笔记（基础之变量、常量和注释）

（附源码）流浪动物保护平台的设计与实现 毕业设计 161154

(免费领源码）Java#Springboot#mysql农产品销售管理系统47627-计算机毕业设计项目选题推荐

（译）计算距离、方位和更多经纬度之间的点

(转) Android中ViewStub组件使用

（转）jdk与jre的区别

(转)Linux整合apache和tomcat构建Web服务器

（转载）VS2010/MFC编程入门之三十四（菜单：VS2010菜单资源详解）

.NET 6 在已知拓扑路径的情况下使用 Dijkstra，A*算法搜索最短路径

.Net Winform开发笔记（一）

.net 无限分类

.Net高阶异常处理第二篇~~ dump进阶之MiniDumpWriter

.Net中ListT 泛型转成DataTable、DataSet

@DataRedisTest测试redis从未如此丝滑

@Data注解的作用

@TableId注解详细介绍 mybaits 实体类主键注解

[ C++ ] STL priority_queue(优先级队列)使用及其底层模拟实现，容器适配器，deque(双端队列)原理了解