Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Авиаперелеты

(Время: 2 сек. Память: 16 Мб Сложность: 48%)

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

Теперь профессор хочет найти путь наименьшей стоимости, учитывая, что до конференции осталось K ночей (то есть профессор может совершить не более K перелетов).

Входные данные

В первой строке входного файла INPUT.TXT находятся целые числа N, M, K, S и F – количество городов, количество авиарейсов, количество оставшихся ночей, номер города, в котором живет профессор, номер города, в котором проводится конференция соответственно (2 ≤ N ≤ 100, 1 ≤ M ≤ 105, 1 ≤ K ≤ 100, 1 ≤ S ≤ N, 1 ≤ F ≤ N).

Далее идет M строк, задающих расписание авиарейсов. i-я строка содержит три натуральных числа: Si, Fi и Pi, где Si – номер города, из которого вылетает i-й рейс, Fi – номер города, в который прилетает i-й рейс, Pi – стоимость перелета i-м рейсом (1 ≤ Si ≤ N, 1 ≤ Fi ≤ N, 1 ≤ Pi ≤ 106).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – минимальную стоимость пути, подходящего для профессора. Если профессор не сможет за K ночей добраться до конференции, выведите число -1.

Пример

INPUT.TXTOUTPUT.TXT
14 5 2 1 4
1 2 1
2 3 1
3 4 1
1 3 3
1 4 5
4

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Алгоритм Флойда
 Алгоритм Форда-Беллмана
 Алгоритм Дейкстры
 Минимальный каркас
 Эйлеров цикл, конденсация
 Паросочетания
 A. Алгоритм Форда-Беллмана
 B. Алгоритм Форда-Беллмана - 2
 C. Цикл отрицательного веса
 D. Цикл отрицательного веса - 2
 E. Рейсы во времени
 F. Авиаперелеты
 G. Лабиринт знаний
 H. Домой на электричках

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru



Как произвести подключение сантехники своими руками?