Прогулка
Задачу добавил: alef
Успешно сдано решений: 0
Маша и ее друзья собрались сходить на лыжах за Волгу. Нужно сказать, что такие прогулки – как на лыжах, так и пешие – в начале марта совершают многие: лед на Волге крепкий, а морозы уже спали. Поэтому от набережной в сторону противоположного берега пролегают как пешеходные тропинки (и автомобильные дорожки, но для нас сейчас разницы между ними нет) и лыжни.
Просто катиться на лыжах друг за другом ребятам показалось скучным. К тому же ходят они все с разной скоростью, да и лыжни разной степени «накатанности». Поэтому друзья договорились, что каждый выбирает лыжню себе по вкусу. А чтобы не разбежаться слишком далеко, назначили встречи в «контрольных точках». Когда кто-то приходит в «контрольную точку», он должен остановиться и дожидаться, пока не соберутся все остальные. Помогите ребятам составить маршруты так, чтобы время, которое дожидается всех остальных первый, пришедший в «контрольную точку» для каждой контрольной точки было минимальным.
Формат входного файла
Первая строка – целое число M (1<=M<=5) – количество ребят (включая Машу), которые отправились на прогулку
Вторая строка содержит через пробел M целых чисел – скорости движения Vr каждого из ребят по идеально накатанной лыжне в м/с (1<=r<=M, 1<=Vr<=10)
Третья – два целых числа N и K; N (1<N<=20) – общее количество точек, между которыми проложены лыжни, K (1<=K<N) – количество «контрольных точек»
Четвертая строка содержит K целых чисел Cj – номера «контрольных точек» через пробел. Лыжники должны собираться вместе в каждой из этих точек; причем в указанном порядке (точек). Если лыжник еще не побывал в точке Cj, то, придя в точку Ci, i<>j, он не должен в ней останавливаться.
В каждой из следующих строк содержится описание очередной лыжни в формате:
два числа I и J (1<=I, J <= N) через пробел – точки, которые соединены данной лыжней, затем через пробел целое число P (0<=P<100), показывающее отклонение степени «накатанности» лыжни от идеальной, и еще через пробел целое число – длина лыжни L в метрах (1<=L<=10000)
В последней строке входного файла содержатся через пробел четыре нуля.
Все лыжники одновременно стартуют из точки №1. По одной лыжне могут двигаться несколько лыжников; в этом случае считается, что лыжники идут упорядоченно по убыванию их скоростей (т.е. первым идет лыжник с наиболее высокой скоростью).
Ни одна пара точек не соединена более чем одной лыжней.
Придя в «контрольную точку», уходить из нее нельзя, не дождавшись всех остальных. Переходя из одной «контрольной точки» в другую, по одной и той же лыжне можно пройти не более одного раза.
Примечание. Отклонение степени «накатанности» лыжни от идеальной уменьшает скорость движения по ней лыжника согласно формуле: V’ = V*(1 – P/100).
Формат выходного файла
В выходном файле содержится K групп строк (по числу «контрольных точек»), отделенных друг от друга пустой строкой.
Каждая группа имеет следующую структуру:
Первая строка – округленное до двух вещественных знаков после запятой число секунд, которые первый пришедший в данную «контрольную точку» лыжник проведет в ожидании всех остальных
Затем следуют M строк (по числу лыжников), в каждой из которых указаны маршруты лыжника до соответствующей контрольной точки (во второй строке группы – маршрут лыжника № 1, в третьей – лыжника № 2 и т.д.). Маршрут лыжника выводится в виде последовательности пройденных им точек от предыдущей «контрольной точки» (либо от точки № 1).
После последней группы пустой строки нет.
Пример входного файла
2
7 10
3 1
3
1 2 10 1000
2 3 5 500
1 3 15 800
0 0 0 0
Пример выходного файла
29.29
1 3
1 2 3