Задача №114036. Непредусмотрительные спелеологи
Однажды группа спелеологов отправилась покорять африканские пещеры. Углубившись достаточно далеко, они обнаружили что-то странное — пахло дымом. «Неужели мы подобрались к вулкану?» — удивленно спросил новичок. «Нет. Около вулкана пахнет серой», — ответил капитан. «Кто у нас занимался тушением костров?». Все неуверенно пожали плечами. «Итак, друзья, мы в ловушке».
Перед капитаном команды спелеологов возникла непосильная задача: как же вывести свою группу из пещеры, не сгорев? Пещера в терминах спелеологов состоит из множества «тоннелей» и «станций». Каждый тоннель соединяет какую-нибудь пару различных станций и имеет свою длину. У капитана имеется карта пещеры, и он знает, где они разводили костры, и где находится выход из пещеры.
Каждую секунду дым распространяется на 1 метр. Таким образом, тоннель длины k , смежный с уже задымленной станцией, заполнится дымом за k секунд, а также заполнится дымом и соответствующая станция. Если спелеологи находятся на станции, где есть дым, они задыхаются. Спелеологи бегут со скоростью 1 метр в секунду. Изначально дым есть только в тех станциях, где спелеологи разводили костры. Перемещаться по тоннелям можно в обе стороны. Если спелеологи прибывают на станцию одновременно с дымом, то они задыхаются (это верно и для той станции, где расположен выход). Гарантируется, что сейчас спелеологи находятся на станции, где нет дыма.
В первой строке входных данных содержится три целых числа N , M и K — количество станций, тоннелей и станций с кострами соответственно ( 2 ≤ N ≤ 2·10 5 , 0 ≤ M ≤ 2·10 5 , 1 ≤ K < N ).
Во второй строке содержится K различных чисел a i — номера станций, в которых спелеологи разводили костры ( 1 ≤ a i ≤ N ).
Следующие M строк описывают тоннели. Каждое описание состоит из трех чисел x i , y i и l i , обозначающих номера станций, которые соединяет i -ый тоннель, и его длину в метрах ( 1 ≤ x i , y i ≤ N , 1 ≤ l i ≤ 10 9 , x i ≠ y i ).
В последней строке входных данных содержится 2 числа S и F — номер станции, на которой сейчас находятся спелеологи и номер станции, в которой находится выход из пещеры ( 1 ≤ S , F ≤ N ).
Выведите единственное число — минимальное количество секунд, которое требуется спелеологам для того, чтобы выбраться из пещеры, либо «-1», если спелеологам не удастся выбраться.
Тесты к этой задаче состоят из четырех групп.
- Тесты 1–2. Тесты из условия, оцениваются в 0 баллов.
- Тесты 3–20. В тестах этой группы N ≤ 10 . Эта группа оценивается в 20 баллов.
- Тесты 21–28. В тестах этой группы все тоннели имеют длину 1. Эта группа оценивается в 20 баллов.
- Тесты 29–35. В тестах этой группы N ≤ 2000 . Эта группа оценивается в 20 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из всех предыдущих групп.
- В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline , т.е. после окончания тура, причем только в случае прохождения всех тестов из всех предыдущих групп.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
6 5 1 6 1 2 20 2 3 2 3 4 1 2 5 1 5 6 3 4 1
23
6 6 2 4 1 4 1 1 6 5 1 2 4 1 1 5 2 5 6 2 5 1 2 3 6
-1