0057. Проблема юного дарования

Имя входного файла:	vasya.in
Имя выходного файла:	vasya.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

Вася готовится к чемпионату мира по новой компьютерной игре <<Зашибалки>>.

Участники перед началом этой игры получают информацию о ее пространстве, которое представляет собой набор площадей, соединенных опасными переходами. Игра начинается с точки старта, и заканчивается по истечению определенного (заданного) времени.

Переходы сторожат страшные Монстры, уничтожение которых приносит очки участнику. Реакция Васи позволяет ему за одну минуту уничтожить всех монстров в любом переходе, соединенном с площадью, на которой он находится, после чего он, используя магическую силу, может мгновенно переместиться на любую площадь (правда использовать он может только переходы, очищенные от монстров).

Единственная проблема Васи – выбор маршрута, который позволит ему получить самое большое количество очков. Как будущему чемпиону мира спланировать свой поход, если известно, что на любую площадь можно попасть с точки старта только одним способом?

Формат входного файла

Первая строка данных задачи – содержит три целых числа: число площадей 1≤ m≤ 200, номер площади, на которой изначально находится Вася (площади занумерованы от 1 до m и время игры T в минутах.

Последующие m - 1 строк содержат описания переходов. Каждый переход описывается тремя числами: первые два – номера площадей, соединенных переходом, а третье – количество очков, получаемое за очистку этого перехода.

Формат выходного файла

Вася – скромный парень, и он даже не надеется, что ему укажут последовательность переходов, его вполне устроит, если в выходном файле вы запишете наибольшее число очков, которые он сможет набрать.

Пример:

vasya.in	vasya.out
9 1 2 3 9 16 3 8 18 5 7 17 5 6 3 4 5 20 2 4 7 2 3 8 1 2 12	20

Источник: Petrozavodsk Winter 2003. Take-Off, Monday, February 03

Обсудить       Отправить решение



Версия для печати