Заходите на сайт www.hood.h15.ru
11.
Задача 6. Красная Шапочка
Входной файл: redhat.in
Выходной файл: redhat.out
Ограничение по времени: 2 сек.
Ограничение по памяти: 64 Мб
Максимальный балл: 100
XVI Всероссийская олимпиада школьников по информатике [2004]
В непроходимом лесу имеется N полянок и M тропинок между
ними. Каждая тропинка соединяет две различные полянки. Две
полянки могут быть соединены несколькими тропинками.
На двух разных полянках живут Красная Шапочка и ее бабушка.
Домик Красной Шапочки находится на полянке с номером 1, а
домик бабушки - на полянке с номером N. Красная Шапочка
хорошо ориентируется в лесу и знает, какое минимальное
время ей потребуется для прохождения каждой тропинки. Когда
Красная Шапочка идет по лесу, она переходит с тропинки на
тропинку только на полянках. На каждой полянке есть
укрытие, в котором Красная Шапочка может спрятаться на
некоторое время.
В этом же лесу живет Волк. Время, за которое Волк пробегает
какую-либо тропинку, может отличаться от времени, за
которое по ней проходит Красная Шапочка. Кроме того, если
Волк пробегает по одной и той же тропинке несколько раз, то
каждый раз он может тратить на это разное время.
С края полянки, где живет Красная Шапочка, Волк увидел, что
она собирается нести пирожки бабушке и побежал по тропинкам
привычного ему пути от дома Красной Шапочки к дому бабушки.
Волк начинает бежать от домика Красной Шапочки в тот
момент, когда она решила выйти из дома, его путь
заканчивается как только он окажется на полянке с домиком
бабушки. Ни на одной полянке Волк не задерживается.
Чтобы застать бабушку в целости и сохранности, Красной
Шапочке необходимо обогнать Волка. При этом ей нельзя
оказаться с Волком на одной тропинке, даже если Волк уже
покидает ее, а она только появляется на ней, или наоборот.
Чтобы избежать встречи с Волком на полянке, Красная Шапочка
использует имеющееся там укрытие. Красной Шапочке нельзя
появляться на полянке одновременно с Волком или покидать
укрытие на полянке в тот момент, когда на ней появляется
Волк. При необходимости Красная Шапочка может идти по
тропинке дольше минимально возможного времени, а также
выйти из дома позже, чем она исходно решила.
Необходимо написать программу, которая поможет Красной
Шапочке добраться к бабушке раньше Волка, если известна
последовательность тропинок, по которым побежал Волк.
Входные данные
Первая строка входного файла содержит числа N, M и K (2 ? N
? 2000, 1 ? M ? 100000, 1 ? K ? 100000). Следующие M строк
содержат по три числа: Bi, Ei - номера полянок, которые
соединяет i-я тропинка, и Ti - минимальное время, за
которое Красная Шапочка может по ней пройти (1 ? Ti ?
10000). В следующих K строках находится последовательное
описание пути Волка, по два числа в строке: Pi - номер
тропинки, по которой он побежит, и Vi - время, которое он
на это затратит (1 ? Vi ? 10000). Путь волка всегда
начинается на полянке 1 и заканчивается на полянке N. Все
числа во входном файле целые и в пределах одной строки
разделены пробелами.
Выходные данные
В том случае, если Красная Шапочка не может добраться до
домика бабушки быстрее Волка, выходной файл должен
содержать слово 'NO'.
Если Красная Шапочка сможет добраться до домика бабушки
быстрее волка, в первой строке выходного файла должно быть
слово 'YES'. Во второй строке в этом случае должно
содержаться число тропинок в пути Красной Шапочки. В третью
строку следует вывести номера тропинок в том порядке, в
котором Красная Шапочка должна по ним пройти. Числа должны
быть разделены пробелами.
Информацию о времени прохождения по тропинкам и остановках
на полянках в выходной файл выводить не нужно.
