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