野餐

Grade 100 Open Time Wednesday, 17 June 2020, 10:25 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 10:25 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 10:25 PM
Input file picnic.in Output file picnic.out

【题目描述】野餐(picnicPKU 1639

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

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

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

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

【输入格式】

第一行是一个整数n,表示小丑与小丑之间及与公园之间的连接数。以下n行表示从A地到B地的路程数,路是双向的,小丑数不会超过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