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

Dmitry Gozman Contest 1. Petrozavodsk training camp. Winter 2007

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

F. Bad Roads

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
В Байтландии есть некоторое количество городов, соединённых дорогами с односторонним движением. К сожалению, состояние дорог оставляет желать лучшего, так что некоторые дороги являются непроходимыми для некоторых автомобилей. Более точно, для каждой дороги известен параметр — минимальная высота просвета для автомобиля, который может проехать по этой дороге. Некоторые дороги являются платными. Плата за проезд по такой дороге равна одному байтландскому тугрику. Также для каждой дороги известно время, которое автомобиль должен потратить, чтобы проехать эту дорогу.
Требуется найти, какая минимальная высота просвета может быть у автомобиля, на котором можно проехать из города s в город f не более, чем за t минут, потратив при этом не более b байтландских тугриков.

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

Первая строка входных данных содержит количество городов n (1 ≤ n ≤ 100), количество дорог m (1 ≤ m ≤ 104), номер стартового города s и финишного города f (1 ≤ s, f ≤ n). Вторая строка содержит максимальную сумму денег, которую можно потратить, b (0 ≤ b ≤ 106) и максимальное время на дорогу t (0 ≤ t ≤ 106).
Каждая из последующих m строк имеет формат ui vi ci ti hi, где ui — город, в котором дорога начинается, vi — город, в котором дорога заканчивается, ci = 1, если дорога платная, и ci = 0 в противном случае, ti — это время, которое требуется для того, чтобы проехать по этой дороге, а hi — минимальный дорожный просвет, требуемый для того, чтобы проехать по этой дороге (1 ≤ ui, vi ≤ n; 0 ≤ ti ≤ 104; 0 ≤ hi ≤ 106). Все числа во входных данных целые.

Результат

Если проехать из s в f, уложившись в ограничения по расходам и по времени, невозможно, выведите −1. Иначе в первой строке выведите минимальную высоту дорожного просвета автомобиля, при которой можно уложиться в ограничения, во второй — количество дорог в каком-либо маршруте, удовлетворяющем ограничениям, а в третьей — номера использованных дорог, перечисленные в порядке прохождения маршрута. Дороги занумерованы последовательными целыми числами от 1 до m в том порядке, в котором они заданы во входных данных.

Примеры

исходные данныерезультат
2 2 1 2     
1 100       
1 2 1 100 77
1 2 1 100 66
66
1
2
2 2 1 2     
0 100       
1 2 0 101 77
1 2 1 100 66
-1
Автор задачи: Dmitry Gozman
Источник задачи: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1527. Bad Roads