This page is still under construction.

Parts of this page are still being built. What you see may change.

Tangled in Cables

Time limit1sMemory limit128 MB

Summary
Compute the minimum spanning tree of a town map and compare its total length against the available spool of cable.
Level

Medium5 of 10

Topics
Minimum spanning tree, Graph, Union-find, Sorting
Solved
No attempts yet

Problem

You are the owner of SmallCableCo and have just bought the franchise rights for a small town. Unfortunately you do not have enough money to start the business properly, so you are relying on parts you found in an old warehouse you purchased. Among your finds is a single spool of cable and a large pile of connectors.

You want to work out whether you have enough cable to connect every house in town. You have a map of the town listing every path you may use to run cable between houses, together with the distance of each path. Compute the shortest total length of cable you need in order to connect all of the houses together.

Input

Only one town is given in the input.

  • The first line gives the length of cable on the spool as a real number.
  • The second line contains the number of houses, NN.
  • The next NN lines each give the name of one house's owner. Each name is at most 20 characters from {a–z, A–Z, 0–9} and contains no whitespace or punctuation.
  • The next line contains MM, the number of paths between houses.
  • The next MM lines each have the form houseA houseB distance. The two house names match two different names in the list above, and the distance is a positive real number. No two paths connect the same pair of houses.

Output

The output consists of a single line.

If there is not enough cable to connect all of the houses in the town, output

Not enough cable

If there is enough cable, output

Need <X> miles of cable

where XX is the shortest total length of cable needed to connect all of the houses, printed to the nearest tenth of a mile (0.1).

Examples3

  1. Example 1

    Input
    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
    Expected output
    Need 10.2 miles of cable

  2. Example 2

    Input
    10.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
    Expected output
    Not enough cable

  3. Example 3

    Input
    10.2
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
    Expected output
    Need 10.2 miles of cable