Модуль: Алгоритм Форда-Беллмана


Задача

6 /6


Лабиринт знаний

Задача

В Летней Компьютерной Школе (ЛКШ) построили аттракцион "Лабиринт знаний". Лабиринт представляет собой N комнат, занумерованных от 1 до N, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход – в комнате N. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.
 
Входные данные:
Первая строка входных данных содержит целые числа N (1 <= N <= 2000) – количество комнат и M (1 <= M <= 10000) – количество дверей. В каждой из следующих M строк содержится описание двери – номера комнат, из которой она ведет и в которую она ведет (через дверь можно ходить только в одном направлении), а также целое число, которое прибавляется к количеству знаний при прохождении через дверь (это число по модулю не превышает 10000). Двери могут вести из комнаты в нее саму, между двумя комнатами может быть более одной двери.
 
Выходные данные:
Выведите ":)" – если можно получить неограниченно большой запас знаний, ":(" – если лабиринт пройти нельзя, и максимальное количество набранных знаний в противном случае.

Примеры
Входные данные Выходные данные
1
2 2
1 2 3
1 2 7
7

 



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6412
Комментарий учителя