|
Имеется телекоммуникационная сеть, состоящая из N приемно-передающих станций (N<100). По объективным причинам надежность передачи сообщений между различными станциями различается. На рисунке показан фрагмент такой сети, содержащий 7 станций.
Дуги соответствуют возможным направлениям передачи сообщений от одной станции к другой. Возле каждой дуги указаны вероятности передачи сообщений без потерь по этим дугам. Необходимо найти маршрут от заданной станции-источника к заданной станции-приемнику с максимальной вероятностью успешной передачи сообщений. Подсчитать также само значение вероятности успешной передачи сообщения по этому маршруту, округленное до четырех десятичных цифр дробной части.
Input
В первой строке содержится 4 целых числа: количество станций N, количество дуг M, номер станции-источника и станции-приемника (различные целые положительные числа, не превышающие N). Далее следуют M строк, каждая из которых содержит информацию об одной дуге сети: номер источника, номер приемника и вероятность успешной передачи сообщения от данного источника к данному приемнику (положительное число, не большее единицы).
Output
Выведите две строки: первая из них содержит последовательность номеров станций, представляющую из себя маршрут передачи сообщения с наибольшей успешностью. Если имеется несколько маршрутов с одинаковой вероятностью успешной передачи сообщений, то вывести любой из них. Маршрут начинается с заданного номера станции-источника и заканчивается заданным номером станции приемника. Вторая строка содержит значение вероятности успешной передачи сообщения по данному маршруту, округленное до четырех знаков после десятичной точки.
Sample
| Input | Output |
7 12 1 7
1 2 0.8
1 3 0.3
1 4 0.65
2 4 0.9
3 4 0.85
2 5 0.5
3 6 0.95
4 5 0.7
4 6 0.6
5 6 0.5
5 7 0.8
6 7 0.9
| 1 2 4 5 7
0.4032 |
|
