2015 German Collegiate Programming Contest (GCPC)
Зміна сценарію
Каждый день Вы едете на работу, используя дороги самого короткого пути. Это эффективно, но со временем Вам надоедает смотреть на одни и те же здания и перекрестки каждый день. Вы решаете искать другие маршруты. Конечно, Вы не хотите жертвовать временем, так что новый путь должен быть столь же коротким как и старый. Существует ли другой путь, который отличается от старого, хотя бы одной улицей?
Входные данные
Первая строка содержит три числа n, m и k (1 ≤ k ≤ n ≤ 104
, 0 ≤ m ≤ 106
), где n количество перекрестков, m количество улиц в городе, а k количество перекрестков которые Вы проезжаете каждый день.
Следующая строка содержит k целых чисел - индексы (начиная с 1) перекрестков которые Вы проезжаете каждый день. Первым перекрестком в этом списке всегда будет 1, а последним всегда будет n. Это будет именно кратчайший путь между 1 и n, проходящий по k перекресткам.
Далее идут m строк. i-ая строка содержит три целых числа ai
, bi
, ci
и описывают улицу от перекрестка ai
до перекрестка bi
длиной ci
(1 ≤ ai
, bi
≤ n, 1 ≤ ci
≤ 104
). Все улицы двунаправленные.
Между одной парой перекрестков может существовать несколько улиц. Кратчайший путь для каждой соседней пары перекрестков a и b использует улицу минимальной длины от a до b.
Выходные данные
Вывести "yes" если существует другой путь такой же длины и "no" иначе.
3 3 3 1 2 3 1 2 1 2 3 2 1 3 3
yes
4 5 2 1 4 1 2 2 2 4 1 1 3 1 3 4 2 1 4 2
no