#P2075. Tangled in Cables

Tangled in Cables

描述:

你是SmallCableCo的老板,购买了一个小镇的特许经营权。不幸的是,你缺乏足够的资金来正常启动业务,只能依靠在一个旧仓库中找到的零件。在你的发现中,有一卷电缆和许多连接器。你想知道你是否有足够的电缆来连接镇上的所有房屋。你有一张小镇的地图,上面标有可以铺设电缆的所有路径及其距离。你需要计算连接所有房屋所需的最短电缆长度。

输入:

输入中只包含一个小镇的数据。

第一行给出电缆卷上的电缆长度,为一个实数。

第二行包含房屋的数量,NN

接下来的NN行给出每个房屋主人的名字。每个名字由最多2020个字符组成(包括aa-zzAA-ZZ00-99),不包含空格或标点符号。

下一行:MM,表示房屋之间的路径数量。

接下来的MM行,每行的格式为: <househouse namename AA> <househouse namename BB> <distancedistance> 其中两个房屋名字与上述列表中的两个不同名字匹配,距离是一个正实数。同一对房屋之间不会有两条路径。

输出:

输出为一行。如果没有足够的电缆连接小镇中的所有房屋,则输出: NotNot enoughenough cablecable 如果有足够的电缆,则输出: NeedNeed <XX> milesmiles ofof cablecable 其中XX精确到小数点后一位(0.10.1)。 输入数据 1

100.0
4
Jones
Smiths
Howards
Wangs
5
Jones Smiths 2.0
Jones Howards 4.2
Jones Wangs 6.7
Howards Wangs 4.0
Smiths Wangs 10.0

输出数据 1

Need 10.2 miles of cable