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

Чемпионат Урала 2013

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

J. Путь к инвестору

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
— Как я мог забыть?! Через T часов нам нужно показать альфа-версию нашей игры потенциальному инвестору. От этой встречи будет зависеть, сможем ли мы завершить разработку игры.
— Без паники! Где мы с ним встречаемся?
— В его офисе, в Тмутаракани. Выезжаем прямо сейчас. Думаю, мы успеем, только в паре мест нужно будет превысить максимальную разрешённую скорость.
— Лишние проблемы с дорожной полицией нам ни к чему — они тоже отнимут время. Сейчас мы придумаем такой маршрут, чтобы успеть вовремя и чтобы максимальное превышение скорости на нём было минимально возможным.

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

В первой строке даны целые числа n и m — количество перекрёстков и дорог между ними (2 ≤ n ≤ 10 000; 1 ≤ m ≤ 10 000). Все дороги двусторонние. В i-й из следующих m строк записаны целые числа ai, bi, si и li, означающие, что между перекрёстками ai и bi есть дорога длиной li километров с максимальной разрешённой скоростью движения si километров в час (1 ≤ ai < bin; 1 ≤ si ≤ 300; 1 ≤ li ≤ 1000). Офис разработчиков игры находится на перекрёстке 1, офис инвестора — на перекрёстке n. Гарантируется, что от перекрёстка 1 до перекрёстка n можно доехать по дорогам. В последней строке записано целое число T — время в часах, оставшееся до встречи (1 ≤ T ≤ 106).

Результат

В первой строке выведите два числа S и k — на сколько километров в час минимум придётся превысить скорость, чтобы успеть на встречу, и количество дорог, по которым нужно будет проехать. Во второй строке через пробел выведите k чисел — номера этих дорог в том порядке, в котором по ним нужно ехать. Дороги пронумерованы целыми числами от 1 до m в соответствии с тем, как они перечислены во входных данных. Если существует несколько способов добраться до офиса инвестора, превысив скорость на S километров в час, можно вывести любой из них. Абсолютная или относительная погрешность S не должна превосходить 10−6.

Примеры

исходные данныерезультат
3 3
1 3 50 150
1 2 80 100
2 3 80 100
2
20.000000 2
2 3
2 1
1 2 60 60
1
0.000000 1
1
Автор задачи: Денис Дублённых
Источник задачи: XVII Открытый чемпионат Урала по спортивному программированию (май, 2013)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1980. Путь к инвестору