数据结构基础

【题目描述】野餐（picnic）PKU 1639

马戏团的小丑们有一个特异功能，无论一个车子有多小，他们都能钻进去，也就是说，一辆车子能够容纳无限个小丑。

现在小丑们要去一个公园野餐，他们住在不同的地方，为了节约能源，要使得所有车子加起来走的路程最小，往往是几个小丑各自开车到另一个小丑家停车后，再挤在一辆车上开车到公园。

但是公园的停车位是有限制的，公园最多只能停k辆车。一旦某个小丑开车到了公园，那么就必须停在公园，不能再回去载其他小丑了。

求所有小丑开车的最短总路程。

【输入格式】

第一行是一个整数n，表示小丑与小丑之间及与公园之间的连接数。以下n行表示从Ａ地到Ｂ地的路程数，路是双向的，小丑数不会超过20人，并且地名的字符长度不会超过10个字符。每一个小丑家到公园的路是连通的，不会出现无解的情况。最后一行是一个整数，表示公园可以容纳的车辆数。

【输出格式】

最小路径数。

【输入样例】

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

【输出样例】

Total miles driven: 183