{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/e7d66346fc0b337fad5f85d5fa5ce673?v\u003d1710944663\"\u003e\u003c/center\u003e\r\u003cbr\u003e拉格里山热带岛的首席长老有一个问题。几年前,一大笔外援资金被用于在村庄之间修建额外的道路。但是丛林不断侵蚀道路,因此庞大的道路网络维护成本太高。长老会必须选择停止维护一些道路。上面左边的地图显示了现在正在使用的所有道路以及维护这些道路每月需要的费用。当然,必须有一种方式可以在维护的道路上连接所有村庄,即使路线不如以前那么短。首席长老希望告诉长老会,他们可以花费的最少金额是多少,以维护连接所有村庄的道路。地图右边显示了以每月216 aacms的最低成本维护的道路。您的任务是编写一个程序来解决这样的问题。\r\u003cbr\u003e\r\u003cbr\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入包括1到100个数据集,后面跟着只包含0的最后一行。每个数据集以一行包含一个数字n开始,表示村庄的数量,1 \u003c n \u003c 27,并且村庄用大写字母表的前n个字母标记。每个数据集由n-1行组成,这些行以字母表顺序开始的村庄标签开头。最后一个村庄没有对应的行。每个村庄的行以该村庄的标签开头,后面是从该村庄通往字母表后面标记的村庄的道路数量k。如果k大于0,则该行继续包含每条道路的数据。每条道路的数据是道路另一端的村庄标签,后面是该道路的每月维护费用(以aacms为单位)。维护费用将是小于100的正整数。每行中的所有数据字段都用单个空格分隔。道路网络将始终允许在所有村庄之间旅行。网络中的道路永远不会超过75条。没有村庄会有超过15条通往其他村庄的道路(字母表中之前或之后的村庄)。在下面的示例输入中,第一个数据集与上面的地图对应。\r\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"输出是每个数据集的每行一个整数:维护连接所有村庄的道路系统的最低费用(以aacms为单位)。注意:一个暴力解决方案,检查每种可能的道路集合,将无法在一分钟的时间限制内完成。\r\u003cbr\u003e"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e9\r\nA 2 B 12 I 25\r\nB 3 C 10 H 40 I 8\r\nC 2 D 18 G 55\r\nD 1 E 44\r\nE 2 F 60 G 38\r\nF 0\r\nG 1 H 35\r\nH 1 I 35\r\n3\r\nA 2 B 10 C 40\r\nB 1 C 20\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e216\r\n30\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}