Входной файл: input2.txt Выходной файл: output2.txt Время на тест: 10 секунд Автор задачи: Котов В.М. Тесты к задаче:Скачать
Внутри пирамиды Хеопса есть N комнат, в которых установлены 2М модулей,
составляющих М устройств. каждое устройство состоит из двух модулей, которые
располагаются в разных комнатах, и предназначено для перемещения между парой
комнат, в которых установлены эти модули. Перемещение происходит за 0.5
условных единицы времени. В начальный момент времени модули всех устройств
переходят в "подготовительный режим". Каждый из модулей имеет
некоторый свой целочисленный период времени, в течение которого он находится в
"подготовительном режиме". По истечении этого времени модуль
мгоновенно "срабатывает" после чего опять переходит в
"подготовительный режим". Устройством можно воспользоваться только в
тот момент, когда одновременно "срабатывают" оба его модуля.
Индиана Джонс сумел проникнуть в гробницу фараона (комната 1). Обследовав
ее, он включил устройства и собрался уходить, но в этот момент проснулся
хранитель гробницы. Теперь Джонсу необходимо как можно быстрее попасть в
комнату N, в которой находится выход из пирамиды. При этом из комнаты в
комнату он может попадать только при помощи устройств, так как проснувшийся
хранитель закрыл все двери в комнатах пирамиды.
Необходимо написать программу, которая получает на входе описания
расположения устройств и их характеристик (смотри описание формата ввода), а
выдает значение оптимального времени и последовательность устройств, которыми
надо воспользоваться, что бы попасть из комнаты 1 в комнату N за это
время.
Формат ввода:
N
M
R11 T11 R12 T12
...
RM1 TM1 RM2 TM2
где
N (2<=N<=100) - количество комнат
M (M<=100) - количество устройств
Ri1 и Ri2 - номера комнат, в которых располагаются модули устройства i
Ti1, Ti2 (Ti1,Ti2<=1000) - периоды времени, через которые срабатывают эти модули
Все числа - натуральные.