Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Привередливый горнолыжник
Любитель горнолыжного спорта Александр решил разнообразить свои серые дни отдыха на горнолыжном курорте. В общей сложности Александр планирует провести на горных склонах K дней. Совершенно очевидно, что при таком отдыхе спуск с одного и того же склона по одному и тому же пути дело более чем скучное, поэтому хотелось бы, чтобы каждый день путь для спуска с горы был бы различным. 
 Спуск состоит из N холмов, которые соединены M дорожками, причем холмы пронумерованы таким образом, что если номер холма A > номера холма B, то дорожка идет вниз от A к B, но не наоборот. Холм номер N – это исходная точка спуска, а холм номер 1 – точка у подножия горы, в которую необходимо осуществить спуск. 
 Александр хотел бы, чтобы каждый из K дней он проходил различный маршрут, причем маршрут должен иметь минимальную длину. Два маршрута считаются различными, если состоят из различных последовательностей дорожек.
Входные данные:
В первой строке входного файла расположено три натуральных числа N (1 ≤ N ≤ 1000), M (1 ≤ M ≤ 10000), K (1 ≤ K ≤ 100) – количество холмов, дорожек и дней отдыха соответственно. 
 Следующие M строк содержат ровно по три натуральных числа Xi, Yi (1≤ Xi, Yi ≤ N), Di (1 ≤ Di ≤ 1000000) – номера холмов, которые соединены дорожкой и длина данной дорожки соответственно.
Выходные данные:
В выходной файл требуется вывести K строк, каждая из которых содержит длину кратчайшего маршрута между холмами N и 1 в i-й день. Если маршрута между холмами не существует, то необходимо вывести число -1.

Пример:
Пути таковы:
(5-1)
(5-3-1)
(5-2-1)
(5-3-2-1)
(5-4-3-1)
(5-4-3-2-1)

Примеры:
input.txt output.txt
1 5 8 7
5 4 1
5 3 1
5 2 1
5 1 1
4 3 4
3 1 1
3 2 1
2 1 1
1
2
2
3
6
7
-1

Сложность задачи: 35%



Проверку могут осуществлять только зарегистрированные пользователи!


Показать обсуждение


На сайте гостей 22, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]