e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

Dijkstra algorithm

106 миль до Чикаго

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

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

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

Первая строка содержит два числа n и m (2n100, 1mn · (n1) / 2), где n - количество перекрестков, m - количество улиц.

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

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

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

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

Подсказка

Самый безопасный путь следующий: 1435

prb1109.gif

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
5 7
5 2 100
3 5 80
2 3 70
2 1 50
3 4 90
4 1 85
3 1 70
Выходные данные #1
61.200000 percent
Источник Летняя Школа 2010, Севастополь, день М.Медведева