野餐计划
   
　　"软体兄弟"是一个著名的小丑马戏团，他们以"用最小的空间中装入众多的小丑"的难以置信的能力而闻名世界。

　　在表演的淡季，小丑们喜欢在本地的公园里进行一年一度的柔术演员聚会。然而小丑们非常的吝啬，他们想找出一种办法，使得所有的小丑到达公园时，花费的路程总数最小。为了达到这个目的，他们决定尽可能多将他们自己装入尽可能少的汽车，使得他们的汽车总路程数最小。这样常常导致许多小丑分别开车到一个小丑的家里，一起挤入其中的一辆汽车。然而在公园里有一强制条件，公园的停车场只能停留有限辆的汽车，这个条件将影响到总的估算。而且由于公园收入场费，一旦任一小丑的汽车到达公园停车场后，它将在停留在停车场，而不能放下乘客，又去载其他小丑。对于这样的一个马戏团，解决这个问题是一个挑战，请你编写一程序解决这样一个运费最小的问题。

　　输入

　　输入文件只包含一个测试数据。第一行是一个整数n，表示连接两个小丑之间或小丑与公园之间的公路的数目。接下来的n行，每行描述一条公路，格式为name1 name2 dist，这里name1 与name2 两个小丑的姓名，或单词'park'与一个小丑的姓名（顺序任意），dist是一个正整数，表示他们之间的距离。这些路是双向的，小丑的个数最多为20，他们的姓名最长为10个字符。最后一行是一个整数s，表示这个公园中最多可停放的汽车数。你可以假设每个小丑到公园都有一条路，问题总是有解的。

　　输出

　　输出包含一行，如下形式：
　　　　Total miles driven: xxx
　　这里xxx是所有小丑汽车行驶总的公里数。

　　Sample Input 1

　　10
　　Alphonzo Bernardo 32
　　Alphonzo Park 57
　　Alphonzo Eduardo 43
　　Bernardo Park 19
　　Bernardo Clemenzi 82
　　Clemenzi Park 65
　　Clemenzi Herb 90
　　Clemenzi Eduardo 109
　　Park Herb 24
　　Herb Eduardo 79
　　3

　　Sample Output 1

　　Total miles driven: 183

　　Sample Input 2

　　10
　　Alphonzo Bernardo 32
　　Alphonzo Park 57
　　Alphonzo Eduardo 43
　　Bernardo Park 19
　　Bernardo Clemenzi 82
　　Clemenzi Park 65
　　Clemenzi Herb 90
　　Clemenzi Eduardo 109
　　Park Herb 24
　　Herb Eduardo 79
　　1

　　Sample Output 2

　　Total miles driven: 255
　　 		   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有