ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Timus Top Coders: Second Challenge

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Российские газопроводы

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ

Вступление

Большими неприятностями обернулся прошедший год для Государства Российского. То неурожай, то птичий грипп, то вечные споры хозяйствующих субъектов... A тут ещё и Президент задумал, наконец, собрать средства на покупку новой балалайки и ручного медведя для своего двоюродного племянника. Все эти факторы (в особенности, конечно, последний) сильно ударили по экономике государства. Посовещавшись со своими друзьями в валенках и ушанках, Президент решил воспользоваться традиционным методом укрепления национального бюджета - увеличением налога на транспортировку газа.

Задача

Сеть российских газопроводов представляет собой N перекачивающих станций, некоторые из которых соединены газопроводами. Для каждого из M газопроводов известны номера станций A[i] и B[i], которые он соединяет, и его прибыльность C[i], т.е. то количество долларов, которое будет ежесуточно приносить в виде налогов перекачка газа по этому газопроводу. Каждая пара станций соединена не более чем одним газопроводом.
Сеть была построена советскими инженерами, которые точно знали, что газ поставляется из месторождений Украины в Сибирь, а не наоборот. Поэтому все газопроводы являются однонаправленными, т.е. для каждого газопровода перекачка газа возможна только в направлении из станции с номером A[i] на станцию с номером B[i]. Более того, для любых двух станций X и Y верно, что если возможна перекачка газа из X на Y (возможно, через промежуточные станции), то обратная перекачка из Y на X невозможна. Известно, что газ поступает на начальную станцию с номером S и отгружается потребителям на конечной станции с номером F.
Президент потребовал от Правительства указать маршрут (т.е. линейную последовательность попарно соединённых газопроводами станций) перекачки газа из начальной станции на конечную, причём прибыльность этого маршрута должна быть максимальной. Под прибыльностью маршрута понимается суммарная прибыльность входящих в него газопроводов.
К сожалению, Президент не учёл того факта, что многие газопроводы изначальной сети уже давно прекратили существование, в результате чего может оказаться, что перекачка газа из начальной станции на конечную вообще невозможна...

Исходные данные

Первая строка содержит целые числа N (2 ≤ N ≤ 500) и M (0 ≤ M ≤ 124750). Каждая из следующих M строк содержит целые числа A[i], B[i] (1 ≤ A[i], B[i] ≤ N) и C[i] (1 ≤ C[i] ≤ 10000) для соответствующего газопровода. Последняя строка содержит целые числа S и F (1 ≤ S, F ≤ N; S ≠ F).

Результат

Если искомый маршрут существует, выведите его прибыльность. Иначе выведите "No solution".

Пример

исходные данныерезультат
6 7
6 5 10
1 4 11
1 2 4
3 1 5
2 4 5
6 3 1
6 1 3
6 4
17

Замечания

В примере искомым маршрутом является маршрут 6>3>1>4.
Автор задачи: Дмитрий Ковалёв, Илья Гребнов, Никита Рыбак
Источник задачи: Timus Top Coders: Second Challenge
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1450. Российские газопроводы