Олимпиада проводится при поддержке Московского физико-технического института, Благотворительного фонда "Династия", компьютерной компании НИКС, Компании Yandex, компании Genius
Информационная поддержка:
журнал "Мир ПК"
III Всероссийская заочная олимпиада школьников по информатике, 2008/09 учебный год
Задача B. Минимальный увеличивающий цикл
| Имя входного файла: | b.in |
| Имя выходного файла: | b.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Разработчики новой игры решили, что игра будет происходить в лабиринте, в котором есть несколько комнат, соединенных между собой телепортами. Телепорты односторонние, то есть, например, если есть телепорт, который ведет из комнаты 1 в комнату 3, то попасть с помощью этого телепорта из комнаты 3 в комнату 1 нельзя. При проходе через телепорт количество очков, набранных участником, увеличивается на некоторую величину (эта величина своя для каждого телепорта). Могут быть телепорты, которые не изменяют количество очков.
Теперь для дальнейшей разработки сценария игры разработчикам в придуманном им лабиринте нужно найти цикл (путь, который начинается и заканчивается в одной и той же комнате, и при этом ни через какую другую комнату не проходит больше одного раза), при прохождении по которому очки участника обязательно увеличатся, а из всех таких циклов нужно выбрать тот, при прохождении по которому очки увеличатся на минимально возможную сумму (если есть несколько таких циклов, можно найти любой из них).
Формат входных данных
Вводится число N - количество комнат в лабиринте (2≤N≤300) и количество телепортов M (0≤M≤N2). Далее идет M троек чисел, описывающих телепорты: Ai, Bi, Ci, что обозначает, что с помощью этого телепорта можно из комнаты Ai попасть в комнату Bi и сумма очков участника при этом изменится на Ci (0≤Ci≤1000). Гарантируется, что для любых двух комнат Q и W существует не более одного телепорта, ведущего из комнаты Q в комнату W (при этом может также существовать и телепорт в обратном направлении), могут быть телепорты из комнаты в нее саму.
Формат выходных данных
Выведите номера комнат в минимальном цикле с положительным суммарным изменением очков участника. Цикл не может проходить через какую-то комнату несколько раз с одним исключением: первая и последняя комната цикла должны совпадать.
Если такого цикла не существует, выведите одно число 0.
Примеры
| b.in | b.out |
5 9 5 2 0 2 1 1 4 1 1 2 5 50 4 5 0 2 4 0 4 3 10 3 3 15 3 5 3 |
5 2 4 3 5 |
4 4 1 2 0 2 3 0 3 1 0 3 4 1 |
0 |