Пикелёв – маленький городок, с малым количеством улочек и совсем без дорожек для бега

6
Пикелёв – маленький городок, с малым количеством улочек и совсем без дорожек для бега. Наташа который день хочет начать бегать по утрам, но каждый раз её останавливает то, что она хочет бегать только по кольцевому маршруту, так как очень любит считать круги, которые пробежала. Наташа знает основные точки в городе, через которые хотела бы пробегать, а также длины дорог между этими маршрутами, однако из-за того, что город маленький, и полиция не патрулирует все дороги должным образом, дороги могут быть как полностью безопасными, так и быть полностью опасными. Наташа не боится опасных дорог, так как занималась много лет боевыми искусствами, но ей хотелось бы, чтобы её маршрут был максимально безопасным, насколько это возможно. Помогите Наташе построить самый большой кольцевой маршрут, который является самым безопасным, с учётом мест, которые она должна посетить 100%. Входные данные На первой строке входного файла подаются три целых числа N (1 <= N <= 100), M (1 <= M <= 1000), K (1 <= K <= 100), где N – количество точек маршрута и M – наборы вида (номер начальной точки (от 1), номер конечной точки (от 1), длина маршрута, степень безопасности (вещественное число [0;1], где 0 – самый небезопасный, 1 – самый безопасный)), K - количество точек маршрута, которые должны быть посещены 100%. Следует учесть, что дороги неориентированные, поэтому, если задан набор (1 2 10 0.5), то значит, что также задан набор (2 1 10 0.5). Выходные данные На выходе необходимо вывести номера вершин самого длинного (с наибольшим количеством точек) кольцевого маршрута (начиная с вершины с меньшим номером, далее выбрать направление к вершине также с меньшим номером из двух возможных), который может быть построен Наташей в её городе, и который проходит минимум через половину вершин, которые Наташа хочет посещать 100%, длину маршрута, а также безопасность маршрута (округлив до двух знаков после запятой; если число целое или имеет один знак, выводить ОБЯЗАТЕЛЬНО С НУЛЯМИ (5.00, 1.70)), при условии, что безопасность маршрута должна быть не менее 0.5. Безопасность маршрута высчитывается как произведение всех значений безопасности каждого пути на маршруте. Если самых больших (с наибольшим количеством точек) кольцевых маршрутов несколько, необходимо вывести самый безопасный. Ввод Вывод 3 3 1 1 2 10 0.8 3 2 5 0.9 1 3 4 1.0 2 1 2 3 19 0.72 4 5 2 1 2 5 1.0 3 1 2 1.0 3 2 2 0.9 4 3 10 0.1 1 4 10 0.1 2 4 1 2 3 9 0.90 Примечание: гарантируется что искомый кольцевой маршрут существует; что могут существовать дороги вокруг одной точки (петли); что никакие две точки маршрута не совпадают; разделитель дробной части всегда ТОЧКА. Пример №2. Наташа имеет 4 точки, 5 дорог и 2 точки, через которые хочет пробегать 100%. При построении максимального кольцевого маршрута, получается кольцо из точек 1 2 3. Видим, что из желаемых 100%-ых точек, Наташа пробегает только через одну, что удовлетворяет условию о пробегании минимум половины. Других кольцевых маршрутов, подходящих под условие задачи нет, поэтому начинаем вывод с самой минимальной вершины (1), далее идём по кольцу в сторону меньшей по значению вершины (2). Длина маршрута 9, а безопасность 0.9.
24 балла
Пикелёв – маленький городок, с малым количеством улочек и совсем без дорожек для бега. Наташа который день хочет начать бегать по утрам, но каждый раз её останавливает то, что она хочет бегать только по кольцевому маршруту, так как очень любит считать круги, которые пробежала. Наташа знает основные точки в городе, через которые хотела бы пробегать, а также длины дорог между этими маршрутами, однако из-за того, что город маленький, и полиция не патрулирует все дороги должным образом, дороги могут быть как полностью безопасными, так и быть полностью опасными. Наташа не боится опасных дорог, так как занималась много лет боевыми искусствами, но ей хотелось бы, чтобы её маршрут был максимально безопасным, насколько это возможно. Помогите Наташе построить самый большой кольцевой маршрут, который является самым безопасным, с учётом мест, которые она должна посетить 100%.


Ввод
3 3 1
1 2 10 0.8
3 2 5 0.9
1 3 4 1.0
2

Вывод
1 2 3 19 0.72

0

0