eolymp
bolt
Try our new interface for solving problems
Məsələlər

Быстрый побег

Быстрый побег

Братья Ньютон планируют ограбить банк в городе Алвизо и хотят найти способ избежать всего лишь одной полицейской машины города. Они знают, что их машина быстрее полицейской. Поэтому если им удастся добраться до одной из магистралей, выходящих из города, то они без особых проблем смогут оторваться от полиции.

Максимальная скорость полицейской машины составляет 160 км/ч. К счастью, братья знают, откуда полицейская машина начнет движение (она припаркована в полицейском участке). Им также известно, что полицейская машина начнет движение, как только они покинут банк и начнут движение на своей машине (момент времени, когда сработает сигнал тревоги).

Братья хотят найти такой маршрут, который будет им гарантировать возможность покинуть город, независимо от того, какой маршрут выберет полицейская машина, и с какой скоростью она будет передвигаться. Поскольку братья чувствуют себя не очень уверенными водителями, то не хотят ехать быстрее, чем это необходимо. К счастью, они недавно инвестировали в новую хай-тек систему отрыва от полицейского автомобиля, которую Вы только что создали. Эта система сообщит Вам минимально необходимую максимальную скорость, достаточную для избегания встречи с полицейской машиной (а также и другие полезные вещи, как например, сам маршрут).

Давайте немного повернем время вспять, когда Вы были заняты построением системы эвакуации из города и сосредоточены на поиске минимальной требуемой скорости. Можете ли Вы найти ее правильно?

Все дороги можно считать бесконечно узкими, а обе машины как точечные объекты. Если браться окажутся в одной точке (на любой дороге или перекрестке) вместе с полицейской машиной, то они будут пойманы. И по закону Мерфи произойдет то что должно произойти. Обе машины начинают движение одновременно и могут ускориться / замедлиться мгновенно в любой момент времени до любой скорости, не большей максимально возможной. Они могут изменять дороги на перекрестках или направление движения в любом месте дороги мгновенно независимо от текущей скорости.

Входные данные

Первая строка содержит три целых числа n (2n100), m (1m5000) и e (1en), где n - количество перекрестков, m - количество дорог в городе, e - количество существующих магистралей. Далее следует m строк, каждая из которых содержит три целых числа a, b, l (1a < bn , 1l100), описывающих дорогу длины l между перекрестками a и b. Далее следует строка из e целых чисел, каждое из промежутка 1...n, описывающих какой из перекрестков соединен с существующей магистралью. Последняя строка содержит два числа b и p (1b, pn и bp), задающих перекрестки, с которых соответственно стартуют братья и полицейская машина.

Всегда есть возможность добраться от одного перекрестка к любому другому. Дороги соединяются только перекрестками (хотя могут пересекаться в других местах используя мосты или тоннели). Дороги двусторонние, между двумя перекрестками может быть не более одной дороги.

Выходные данные

Вывести наименьшую скорость в км/ч, достаточную для того чтобы убежать из города, или слово IMPOSSIBLE, если это невозможно. В первом случае вывести ответ с точностью 10-9.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3 2 1
1 2 7
2 3 8
1
3 2
Çıxış verilənləri #1
IMPOSSIBLE
Giriş verilənləri #2
3 2 1
1 2 7
2 3 8
1
2 3
Çıxış verilənləri #2
74.666666667
Giriş verilənləri #3
4 4 2
1 4 1
1 3 4
3 4 10
2 3 30
1 2
3 4
Çıxış verilənləri #3
137.142857143
Mənbə 2009 Nordic Collegiate Programming Contest, October 3, Problem E