e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

2015 German Collegiate Programming Contest (GCPC)

Зміна сценарію

Каждый день Вы едете на работу, используя дороги самого короткого пути. Это эффективно, но со временем Вам надоедает смотреть на одни и те же здания и перекрестки каждый день. Вы решаете искать другие маршруты. Конечно, Вы не хотите жертвовать временем, так что новый путь должен быть столь же коротким как и старый. Существует ли другой путь, который отличается от старого, хотя бы одной улицей?

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

Первая строка содержит три числа n, m и k (1kn104, 0m106), где n количество перекрестков, m количество улиц в городе, а k количество перекрестков которые Вы проезжаете каждый день.

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

Далее идут m строк. i-ая строка содержит три целых числа ai, bi, ci и описывают улицу от перекрестка ai до перекрестка bi длиной ci (1ai, bin, 1ci104). Все улицы двунаправленные.

Между одной парой перекрестков может существовать несколько улиц. Кратчайший путь для каждой соседней пары перекрестков a и b использует улицу минимальной длины от a до b.

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

Вывести "yes" если существует другой путь такой же длины и "no" иначе.

prb7710.gif

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 3 3
1 2 3
1 2 1
2 3 2
1 3 3
Вихідні дані #1
yes
Вхідні дані #2
4 5 2
1 4
1 2 2
2 4 1
1 3 1
3 4 2
1 4 2
Вихідні дані #2
no
Джерело 2015 German Collegiate Programming Contest (GCPC), June 20, Problem E