Нужно найти путь с максимальной вероятностью быть не пойманными

В фильме "Братья Блюз" детский дом, в котором воспитывались Элвуд и Джек, должен быть продан Совету по Образованию, если они только не уплатят 5000 долларов налогов в офисе Кука в Чикаго. Сыграв концерт в Палас Отеле и заработав 5000 долларов, им надо найти дорогу в Чикаго. Но это не так просто как кажется, так как за ними гонится полиция, местная банда и группа нацистов. Более того, до Чикаго 106 миль, уже темно, а они носят темные очки.

Поскольку у них миссия от Бога, Вы должны помочь найти им самый безопасный путь в Чикаго. Самым безопасным считается путь, на котором вероятность быть не пойманными максимальна.

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

Первая строка содержит два числа n и m (2 ≤ n ≤ 100 , 1 ≤ m ≤ n·(n – 1)/2). n – количество перекрестков, m – количество улиц.

Следующие m строк описывают улицы. Каждая улица описывается тремя целыми числами a, b и p (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ p ≤ 100): a и b – концы улицы, а p – вероятность в процентах того что Братья Блюз пройдут по улице незамеченными. Все улицы двусторонние. Между любыми двумя перекрестками существует не более одной улицы.

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

Вычислить вероятность выбора безопасной дороги от перекрестка 1 (Палас Отель) до перекрестка n (плаза Дж. Дейли в Чикаго). Считайте, что хотя бы один такой путь обязательно существует между перекрестками 1 и n.

Искомую вероятность следует вывести в процентах с 6 знаками после десятичной запятой. Результат выводить следует в формате, приведенном ниже.

Подсказка

Самый безопасный путь следующий: 1 → 4 → 3 → 5

Входные данные
5 7
5 2 100
3 5 80
2 3 70
2 1 50
3 4 90
4 1 85
3 1 70
Выходные данные
61.200000 percent
Ребят, помогите пожалуйста, срочно надо!!!

0

То что вам нужно с поправкой на расчет весов, т.е вместо суммы - произведение, а вместо минимального - максимальный.

0