Беспорядки и маршруты
В стране с
n городами имеется m дорог, соединяющих эти города. У каждой дороги есть вероятность (0 ≤ ≤ 1) того, что она будет открыта, несмотря на продолжающиеся беспорядки. Сами города всегда доступны. Ваша задача — найти маршрут из города 1 в город n, который даст максимально возможную вероятность того, что все дороги на этом маршруте будут открыты. Если никакого пути из города 1 в город n не существует, полагается, что вероятность равна 0.Напишите программу, которая определяет максимальную вероятность того, что маршрут от города
1 до города n окажется открытым.Входные данные
Первая строка содержит два целых числа
n и m, разделённые пробелом (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 20 000). Эти числа означают количество городов и количество дорог соответственно.Каждая из следующих
m строк содержит три числа: , и (, ). Эти данные описывают одну дорогу между городами и , а также вероятность , что она будет открыта.Выходные данные
Выведите одно вещественное число, представляющее собой максимальную вероятность того, что путь от города
1 до города n будет открытым. Ваш ответ будет считаться верным, если его абсолютное или относительное отклонение от правильного результата не превысит 1e-5.Примеры
Input | Output |
4 4
1 2 0.90
2 3 0.80
3 4 0.70
1 4 0.45 | 0.50400 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB