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

6
Пикелёв – маленький городок, с малым количеством улочек и совсем без дорожек для бега. Наташа который день хочет начать бегать по утрам, но каждый раз её останавливает то, что она хочет бегать так, чтобы не пробегать по кольцевому маршруту (не пробегать через какую-либо точку два раза), так как не любит пробегать по одним и тем же точкам несколько раз. Наташа знает основные точки в городе, через которые хотела бы пробегать, а также длины дорог между этими маршрутами, однако из-за того, что город маленький, и полиция не патрулирует все дороги должным образом, дороги могут быть как полностью безопасными, так и быть полностью опасными. Наташа не боится опасных дорог, так как занималась много лет боевыми искусствами, но ей хотелось бы, чтобы её маршрут был максимально безопасным, насколько это возможно. Помогите Наташе построить самый длинный маршрут без циклов, который является самым безопасным. Входные данные На первой строке входного файла подаются два целых числа N (1 <= N <= 100) и M (1 <= M <= 1000), где N – количество точек маршрута и M – наборы вида (номер начальной точки (от 1), номер конечной точки (от 1), длина маршрута, степень безопасности (вещественное число [0;1], где 0 – самый небезопасный, 1 – самый безопасный)) Следует учесть, что дороги неориентированные, поэтому, если задан набор (1 2 10 0.5), то значит, что также задан набор (2 1 10 0.5). Выходные данные На выходе необходимо вывести номера вершин самого длинного маршрута без циклов (начиная с вершины с самым меньшим номером), который может быть построен Наташей в её городе, длину маршрута, а также безопасность маршрута (с точностью до двух знаков), при условии, что безопасность маршрута должна быть не менее 0.5. Безопасность маршрута высчитывается как произведение всех значений безопасности каждого пути на маршруте. Если самых длинных маршрутов несколько, необходимо вывести самый безопасный. Ввод Вывод 3 3 1 2 10 0.8 3 2 5 0.4 1 3 4 1.0 2 1 3 14 0.8 6 7 1 2 10 0.8 2 3 5 0.9 6 3 20 1.0 4 2 8 0.2 3 4 7 0.7 4 6 9 1.0 5 4 2 1.0 1 2 3 6 4 5 46 0.72 Примечание: гарантируется что искомый маршрут существует; что могут существовать дороги вокруг одной точки (петли); что никакие две точки маршрута не совпадают; разделитель дробной части всегда ТОЧКА.
24 балла
Пикелёв – маленький городок, с малым количеством улочек и совсем без дорожек для бега. Наташа который день хочет начать бегать по утрам, но каждый раз её останавливает то, что она хочет бегать так, чтобы не пробегать по кольцевому маршруту (не пробегать через какую-либо точку два раза), так как не любит пробегать по одним и тем же точкам несколько раз. Наташа знает основные точки в городе, через которые хотела бы пробегать, а также длины дорог между этими маршрутами, однако из-за того, что город маленький, и полиция не патрулирует все дороги должным образом, дороги могут быть как полностью безопасными, так и быть полностью опасными. Наташа не боится опасных дорог, так как занималась много лет боевыми искусствами, но ей хотелось бы, чтобы её маршрут был максимально безопасным, насколько это возможно. Помогите Наташе построить самый длинный маршрут без циклов, который является самым безопасным.



Входные данные

На первой строке входного файла подаются два целых числа N (1 <= N <= 100) и M (1 <= M <= 1000), где N – количество точек маршрута и M – наборы вида (номер начальной точки (от 1), номер конечной точки (от 1), длина маршрута, степень безопасности (вещественное число [0;1], где 0 – самый небезопасный, 1 – самый безопасный)) Следует учесть, что дороги неориентированные, поэтому, если задан набор (1 2 10 0.5), то значит, что также задан набор (2 1 10 0.5).



Выходные данные

На выходе необходимо вывести номера вершин самого длинного маршрута без циклов (начиная с вершины с самым меньшим номером), который может быть построен Наташей в её городе, длину маршрута, а также безопасность маршрута (с точностью до двух знаков), при условии, что безопасность маршрута должна быть не менее 0.5. Безопасность маршрута высчитывается как произведение всех значений безопасности каждого пути на маршруте. Если самых длинных маршрутов несколько, необходимо вывести самый безопасный.
Ввод
3 3

1 2 10 0.8

3 2 5 0.4

1 3 4 1.0
Вывод
2 1 3 14 0.8

0

Чо, правда думаешь, что тут все бросятся за тебя решать твои олимпиадные задачи?

0