printРабочее место участника

printЗадачи

2386. Встреча

Ограничения: время – 500ms/1000ms, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Финну нужно срочно встретиться с Принцессой Бубльгум, которая в данный момент совершает утреннюю пробежку по круговому маршруту.
Напишите программу, которая найдет минимальное время до встречи Финна и Принцессы.
Формат ввода
Первая строка ввода содержит одно целое число — количество дорог `M` (`2\ ≤\ M\ ≤\ 100000`). Далее следует `M` строк, содержащих по три целых числа — номера перекрестков `a_i` и `b_i`, которые соединяет дорога, и длина дороги `c_i` (`1\ ≤\ a_i,\ b_i,\ c_i\ ≤\ 5000`, `a_i\ ≠\ b_i`). Далее следует строка, содержащая два целых числа — скорость Принцессы `V_P` (`1\ ≤\ V_P\ ≤\ 100`) и количество дорог `K` (`2\ ≤\ K\ ≤\ 1000`), по которым пробегает Принцесса. Следующая строка содержит `K+1` целое число — последовательность номеров перекрестков в маршруте Принцессе. Первый и последний номера в маршруте совпадают. В начальный момент времени Принцесса находится на первом перекрестке маршрута. В следующей строке содержится два целых числа — скорость Финна `V_F` (`1\ ≤\ V_F\ ≤\ 100`) и номер перекрестка `S` (`1\ ≤\ S\ ≤\ 5000`), на котором находится Финн в начальный момент времени. Гарантируется, что маршрут Принцессы проходит по существующим дорогам, между перекрестками не более одной дороги, и есть путь от `S` до маршрута Принцессы.
Формат вывода
Вывести одно вещественное число — время до встречи Финна с Принцессой с точностью `10^{-2}`.

Пример ввода

4
1 2 4
2 3 5
3 4 3
2 4 3
4 3
2 3 4 2
2 1

Пример вывода

2.50
loading