시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 64 MB | 0 | 0 | 0 | 0.000% |
В непроходимом лесу имеется $N$ полянок и $M$ тропинок между ними. Каждая тропинка соединяет две различные полянки. Две полянки могут быть соединены несколькими тропинками.
На двух разных полянках живут Красная Шапочка и ее бабушка. Домик Красной Шапочки находится на полянке с номером $1$, а домик бабушки --- на полянке с номером $N$. Красная Шапочка хорошо ориентируется в лесу и знает, какое минимальное время ей потребуется для прохождения каждой тропинки. Когда Красная Шапочка идет по лесу, она переходит с тропинки на тропинку только на полянках. На каждой полянке есть укрытие, в котором Красная Шапочка может спрятаться на некоторое время.
В этом же лесу живет Волк. Время, за которое Волк пробегает какую-либо тропинку, может отличаться от времени, за которое по ней проходит Красная Шапочка. Кроме того, если Волк пробегает по одной и той же тропинке несколько раз, то каждый раз он может тратить на это разное время.
С края полянки, где живет Красная Шапочка, Волк увидел, что она собирается нести пирожки бабушке и побежал по тропинкам привычного ему пути от дома Красной Шапочки к дому бабушки. Волк начинает бежать от домика Красной Шапочки в тот момент, когда она решила выйти из дома, его путь заканчивается как только он окажется на полянке с домиком бабушки. Ни на одной полянке Волк не задерживается.
Чтобы застать бабушку в целости и сохранности, Красной Шапочке необходимо обогнать Волка. При этом ей нельзя оказаться с Волком на одной тропинке, даже если Волк уже покидает ее, а она только появляется на ней, или наоборот. Чтобы избежать встречи с Волком на полянке, Красная Шапочка использует имеющееся там укрытие. Красной Шапочке нельзя появляться на полянке одновременно с Волком или покидать укрытие на полянке в тот момент, когда на ней появляется Волк. При необходимости Красная Шапочка может идти по тропинке дольше минимально возможного времени, а также выйти из дома позже, чем она исходно решила.
Необходимо написать программу, которая поможет Красной Шапочке добраться к бабушке раньше Волка, если известна последовательность тропинок, по которым побежал Волк.
Первая строка входного файла содержит числа $N$, $M$ и $K$ ($2 \le N \le 2\,000$, $1 \le M \le 100\,000$, $1 \le K \le 100\,000$). Следующие $M$ строк содержат по три числа: $B_i$, $E_i$ --- номера полянок, которые соединяет $i$-я тропинка, и $T_i$ --- минимальное время, за которое Красная Шапочка может по ней пройти ($1 \le T_i \le 10\,000$).
В следующих $K$ строках находится последовательное описание пути Волка, по два числа в строке: $P_i$ --- номер тропинки, по которой он побежит, и $V_i$ --- время, которое он на это затратит ($1 \le V_i \le 10\,000$). Путь волка всегда начинается на полянке 1 и заканчивается на полянке $N$.
Все числа во входном файле целые и в пределах одной строки разделены пробелами.
В том случае, если Красная Шапочка не может добраться до домика бабушки быстрее Волка, выходной файл должен содержать слово "NO
".
Если Красная Шапочка сможет добраться до домика бабушки быстрее волка, в первой строке выходного файла должно быть слово "YES
". Во второй строке в этом случае должно содержаться число тропинок в пути Красной Шапочки. В третью строку следует вывести номера тропинок в том порядке, в котором Красная Шапочка должна по ним пройти. Числа должны быть разделены пробелами.
Информацию о времени прохождения по тропинкам и остановках на полянках в выходной файл выводить не нужно.
4 4 5 1 3 6 1 2 2 2 3 2 3 4 1 2 1 2 2 2 1 3 4 4 1
YES 2 1 4
4 3 4 1 2 2 2 3 1 2 4 3 1 2 2 1 2 2 3 5
NO