Отъезд (20 баллов)
Автор задачи: Александр Ефимов
Задачу добавил: alef
Успешно сдано решений: 12
Семинар окончен, и NN собирается выехать поездом из города MM. Он приобрел билет заранее, но в день отъезда обнаружил, что добрая кассирша указала в нем не совсем этот день. И ему приходится срочно отправиться на вокзал менять билеты, попутно прикидывая, как побыстрее добраться.
Самый надежный способ - ехать на метро: поезда не окажутся в пробке. Однако по дороге к метро из новостей по радио он узнает, с каких станций метро поступила информация о, возможно, заложенных взрывных устройствах. Найдите самый короткий маршрут, а если таких окажется несколько - выберите самый безопасный из них.
Формат входного файла input.txt
Первая строка - целое число S - количество станций метро.
Следующие S строк описывают схему метро таким образом.
Каждая строка содержит несколько пар целых чисел вида (J, T). Первое число в паре - J - номер станции, второе число - T - время в минутах, за которое можно добраться от текущей станции до станции J. Перечислены только станции, которые связаны непосредственно друг с другом.
Формат выходного файла output.txt
Первая строка S целых чисел - номера станций, составляющих наиболее безопасный из наиболее коротких маршрутов.
Пример входного файла
Пример выходного файла