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 знаками після десяткової коми. Результат слід виводити у форматі, наведеному нижче.

Підказка

Найбезпечніший шлях наступний: 1 → 4 → 3 → 5

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, Севастополь, день М.Медвєдева