Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Отъезд (20 баллов)

Автор задачи: Александр Ефимов

Задачу добавил: alef

Успешно сдано решений: 12

Семинар окончен, и NN собирается выехать поездом из города MM. Он приобрел билет заранее, но в день отъезда обнаружил, что добрая кассирша указала в нем не совсем этот день. И ему приходится срочно отправиться на вокзал менять билеты, попутно прикидывая, как побыстрее добраться.
Самый надежный способ - ехать на метро: поезда не окажутся в пробке. Однако по дороге к метро из новостей по радио он узнает, с каких станций метро поступила информация о, возможно, заложенных взрывных устройствах. Найдите самый короткий маршрут, а если таких окажется несколько - выберите самый безопасный из них.

Формат входного файла input.txt
Первая строка - целое число S - количество станций метро.
Следующие S строк описывают схему метро таким образом.
Каждая строка содержит несколько пар целых чисел вида (J, T). Первое число в паре - J - номер станции, второе число - T - время в минутах, за которое можно добраться от текущей станции до станции J. Перечислены только станции, которые связаны непосредственно друг с другом.

Формат выходного файла output.txt
Первая строка S целых чисел - номера станций, составляющих наиболее безопасный из наиболее коротких маршрутов.

Пример входного файла

Пример выходного файла

Сдать задачу

Задать вопрос жюри по этой задаче