ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1934. Чёрная метка

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Прихлоп: Ужасное чудовище Джонса найдёт тебя, утащит «Жемчужину» в пучину, и тебя вместе с ней.
Джек: Не знаешь, когда Джонс выпустит из клетки свою зверюшку?
Прихлоп: Я уже сказал, Джек. Твой срок вышел. Он уже рыщет, им движет неодолимое желание сожрать обладателя чёрной метки.
На руке у капитана Джека Воробья красуется чёрная метка, и он избегает выхода в открытое море, потому что там его поджидает морское чудище Кракен. Но свободолюбивая натура пирата не позволяет ему усидеть на одном месте. И вот Джек собирается на Тортугу.
В Карибском море есть n островов. Джек собирается добираться до Тортуги, переправляясь с острова на остров по маршрутам, которые позволяют выходить в открытое море только на небольшие промежутки времени. Для некоторых пар островов Джеку известны такие маршруты, но они всё равно могут представлять опасность — на каждом таком маршруте есть некоторая вероятность встретить Кракена.
Джек очень торопится и хочет добраться до Тортуги, посетив при этом минимально возможное количество островов. Если таких путей несколько, то он хочет следовать тем из них, на котором вероятность встречи с Кракеном минимальна. Но Джека устроит любой путь, проходящий через наименьшее количество островов, на котором вероятность встретить Кракена отличается от оптимальной не более чем на 10−6. Помогите Джеку найти такой путь.

Исходные данные

В первой строке даны два целых числа n и m — количество островов и известных маршрутов между ними соответственно (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). Во второй строке находятся два целых числа s и t — номер острова, на котором находится Джек, и номер Тортуги (1 ≤ s, tn; st). В каждой из следующих m строк записано по три целых числа — номера островов ai и bi, между которыми известен маршрут, и pi — вероятность встретить Кракена на этом маршруте в процентах (1 ≤ ai, bin; aibi; 0 ≤ pi ≤ 99). Между каждой парой островов известно не более одного маршрута. Гарантируется, что от острова, на котором находится Джек, до Тортуги существует хотя бы один путь по известным маршрутам.

Результат

В первой строке выведите через пробел числа k и p — количество островов в пути и вероятность встретить Кракена на этом пути. p должно быть выведено с абсолютной погрешностью не более 10−6. В следующей строке следует вывести k чисел, разделённых пробелами — номера островов в порядке следования. Если существует несколько решений, то выведите любой из них.

Пример

исходные данныерезультат
4 4
1 3
1 2 50
2 3 50
1 4 10
4 3 10
3 0.19
1 4 3
Автор задачи: Денис Дублённых (подготовка — Егор Щелконогов)
Источник задачи: Открытый командный чемпионат УрФУ по программированию — 2012