#255. Picnic Planning

Picnic Planning

题目描述

给定用名称表示顶点的无向带权图,特殊顶点名为 Park。求一棵生成树,要求与 Park 相连的树边不超过 K 条,且总边权最小。

输入格式

先输入边数,再逐行输入两个顶点名称和边权;最后输入 K。

输出格式

按 Total miles driven: X 的格式输出最小总边权。

样例输入

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

题意整理;原题与输入输出格式对照。