This page is still under construction.

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

Picnic Planning

Time limit1sMemory limit128 MB

Summary
Find a minimum-cost set of car routes so every brother reaches Park, with at most s cars parked there.
Level

Hard8 of 10

Topics
Graph, Minimum spanning tree, Greedy, Math
Solved
No attempts yet

Problem

The Contortion Brothers are a famous troupe of circus clowns, known worldwide for their incredible ability to cram an unlimited number of themselves into even the smallest vehicle. During the off-season, the brothers like to get together for their annual meeting at a local park (referred to as Park).

The brothers are tight not only about cramped quarters but with money as well, so they want to travel to the meeting in the way that minimizes the total number of miles put on all of their cars combined (saving gas, wear and tear, and so on). To this end they are willing to squeeze into as few cars as necessary. This often results in several brothers driving to one brother's house, leaving all but one car there, and piling into the remaining car.

There is a constraint at the park, however: the parking lot at the picnic site can hold only a limited number of cars, and this must be factored into the overall minimization. Also, because of an entrance fee, once any brother's car arrives at the park it stays there; a brother will not drop off his passengers and then leave to pick up others.

Given the network of roads connecting the brothers' houses and the park, determine the minimum possible total mileage such that every brother reaches the park, while the number of cars that arrive at the park does not exceed the parking-lot capacity.

Input

The input begins with a single positive integer on a line by itself, indicating the number of test cases that follow. This line is followed by a blank line, and there is also a blank line between two consecutive test cases.

Each test case is one problem instance:

  • The first line contains a single integer nn, the number of road connections between brothers or between a brother and the park.
  • Each of the next nn lines contains one connection in the form name1 name2 dist, where name1 and name2 are either the names of two brothers or the word Park together with a brother's name (in either order), and dist is the integer distance between them.
  • All roads are two-way, and dist is always positive.
  • The final line contains an integer ss, the number of cars that can fit in the parking lot of the picnic site.

There are at most 20 brothers, and each name is at most 10 characters long. You may assume that there is a path from every brother's house to the park and that a solution exists for every test case.

Output

For each test case, print a single line of the form

Total miles driven: xxx

where xxx is the total number of miles driven by all the brothers' cars. Separate the outputs of two consecutive test cases with a blank line.

Examples2

  1. Example 1

    Input
    2

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

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
1
    Expected output
    Total miles driven: 183

Total miles driven: 255

  2. Example 2

    Input
    1

1
Alice Park 10
1
    Expected output
    Total miles driven: 10