G. Tesla Model S

Имя входного файла: stdin
Имя выходного файла: stdout
Ограничение по времени: 2 s
Ограничение по памяти: 256 megabytes

Джон купил новый автомобиль – Tesla Model S. Как известно, этот автомобиль надо заряжать на специальных заправочных станциях, которые называются <<SuperCharger>>. Такая станция позволяет зарядить автомобиль Tesla за 20 минут – что не сильно отличается от времени заправки обычного автомобиля.

Джон, как истинный американец, любит путешествовать на своей машине по стране. Однако сеть заправок SuperCharger пока развита не так сильно, и иногда путешествие из одного города в другой с использованием таких заправок невозможно.

Джон составил карту автодорог США, отметил на ней заправки SuperCharger и теперь интересуется, можно ли из одного заданного города доехать в другой, возможно, используя заправки SuperCharger. Его не интересует кратчайший путь – любой путь, позволяющий проехать с использованием заправок SuperCharger, его устроит. Изначально машина Джона полностью заряжена.

Формат входного файла

В первой строке ввода находятся четыре числа N, M, K, P – количество городов, количество дорог между городами, количество городов, в которых есть заправка SuperCharger и расстояние, которое Tesla Model S может проехать на полностью заряженном аккумуляторе (1 ≤ N ≤ 105, 1 ≤ M ≤ 3⋅105, 1 ≤ K ≤ N, 1 ≤ P ≤ 109).

Во второй строке находится K чисел – номера городов, в которых есть заправка SuperCharger. Города нумеруются с единицы.

Далее следует M строк – описания дорог на карте. Каждая дорога описывается тремя числами ai, bi, ci – номера городов, которые она соединяет и длина дороги (1 ≤ ai, bi ≤ N, 1 ≤ ci ≤ 109).

Город, в котором Джон начинает путешествие, имеет номер 1, город, в котором он финиширует, имеет номер N. В начале путешествия машина Джона полностью заряжена.

Формат выходного файла

В первой строке выведите число T – количество городов, которые потребуется посетить Джону, чтобы доехать из города 1 в город N. Во второй строке выведите номера этих городов в порядке посещения. Помните, что Джон не требует найти кратчайший путь, однако расстояние, пройденное между дозаправками, должно быть не более P. Если возможных путей несколько, выведите любой из них. Изначально автомобиль Джона полностью заряжен. В пути, который вы выведете, не должно быть больше, чем 3 ⋅106 вершин.

Если доехать из города 1 в город N невозможно, выведите единственное число -1.

Пример:

4 4 1 10 2 1 4 11 1 2 9 2 3 5 3 4 5 4 1 2 3 4
6 7 3 5 1 2 3 1 2 1 2 3 1 3 1 1 3 4 4 4 5 1 5 6 1 4 6 2 -1
3 3 0 3 1 2 1 2 3 1 1 3 1 3 1 2 3

В первом примере дорога из города 1 в город 4 слишком длинная, чтобы проехать её на одной заправке, поэтому Джону приходится ехать в объезд.

Во втором примере Джон может доехать до городов 1, 2, 3, 4, 5, но на дорогу до последнего города ему не хватает заряда.

Третий пример показывает, что кратчайший путь искать необязательно.


Источник: Чемпионат ПетрГУ по программированию. Октябрь 2014.

Обсудить       Отправить решение



Версия для печати