Планирование пикника
Планирование пикника
Братья Конторсия - знаменитая труппа цирковых клоунов, известных во всем мире своими невероятными способностями втискивать неограниченное количество себя в даже самый маленький автомобиль. В межсезонье братья любят собираться на ежегодное собрание Конкортиционистов в местном парке. Братья ощущают трудности не только в отношении тесноты, но и в отношении денег, поэтому они пытаются найти способ привлечь всех к вечеринке, что сводит к минимуму количество миль, пройденных всеми автомобилями (таким образом, экономя газ, износ, амортизацию и т. д.). Для этого они готовы втиснуться в несколько автомобилей, необходимых для минимизации общего количества миль на всех своих автомобилях. Это часто приводит к тому, что один брат едет в дом другого брата, оставляет там свой автомобиль и пересаживается в автомобиль брата. Однако в парке есть ограничение: на стоянке на площадке для пикников может быть только ограниченное количество автомобилей, поэтому это следует учитывать при расчете. Кроме того, из-за оплаты въезда в парк, при прибытии в парк автомобиля любого брата, он должен там остаться; нельзя высадить пассажиров и поехать забрать других братьев. Ваша цирковая труппа должна решить эту непростую задачу, поэтому Вам остается написать программу для решения проблемы минимизации пройденных миль.
Входные данные
Первая строка содержит число n - количество дорог между братьями или между братьями и парком. Каждая из следующих n строк содержит описание дороги в виде name1 name2 dist, где name1 и name2 - имена двух братьев или имя брата и слово Park (в любом порядке), dist - расстояние между ними. Дороги являются двусторонними, dist всегда положительно. Максимальное количество братьев равно 20, наибольшая длина их имен содержит до 10 символов. За этими n строками следует последняя строка содержащая целое число s - количество машин, которое может поместиться на стоянке места для пикника. Считайте, что всегда существует путь от дома каждого брата до парка и что решение всегда существует.
Выходные данные
Выведите строку в виде
Total miles driven: xxx
где xxx - общее количество миль, пройденных всеми машинами братьев.
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
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
Total miles driven: 255