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

Открытое личное первенство УрГУ 2006

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

D. Автобусы города Васюки

Ограничение времени: 1.5 секунды
Ограничение памяти: 64 МБ
Университет города Васюки добился права провести у себя четвертьфинальное соревнование ACM, и организаторы хотят, чтобы все было на высшем уровне. Они подготовили для участников буклеты с полезной информацией, не забыв разместить там схему движения городского транспорта. Правда, городской транспорт представлен в Васюках только сетью автобусных маршрутов, но васюкинцы верят, что все у них впереди.
Университет города Петюки добился права отправить свою команду на четвертьфинальное соревнование в город Васюки. Правда, с финансированием у них туговато, так что приходится экономить. Поэтому петюкинские студенты решили передвигаться по Васюкам, используя наименьшее количество пересадок, ведь за одну поездку на каждом из маршрутов приходится платить один рубль (независимо от количества остановок). И это каждому из студентов, а их в команде трое. Хорошо хоть, за тренера не надо платить, он вообще не поехал в Васюки, на него денег не хватило. А ходить пешком студентам неохота. Им проще написать программку расчета самого экономичного маршрута, чем пройти лишний километр, да и быстрее. Или не быстрее? За сколько времени можно написать такую программу?
P.S. Пешеход проходит один километр в среднем за 12 минут.

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

Первая строка входа содержит 2 числа: количество автобусных маршрутов в городе Васюки N и количество различных остановок M (1 ≤ N ≤ 1000; 1 ≤ M ≤ 105; остановки пронумерованы от 1 до M). Далее следуют N строк c описанием автобусных маршрутов. Каждая из этих строк начинается с количества остановок данного маршрута, а далее идут номера этих остановок. Суммарное количество чисел в строках с 2 по N+1 не превосходит 200000. (N+2)-я строка содержит два числа A и B — номера начальной и конечной остановок (числа A и B не совпадают).

Результат

Если от остановки A до остановки B невозможно проехать на автобусах, то выведите −1. В противном случае в первой строке выведите минимальную сумму (в рублях), необходимую для проезда одного человека от A до B, а во второй строке необходимо описать один из возможных маршрутов с этой стоимостью, перечислив остановки, на которых нужно делать пересадки (включая начальную и конечную).

Пример

исходные данныерезультат
3 10
5 2 4 6 8 10
3 3 6 9
2 5 10
5 9
3
5 10 6 9
Автор задачи: Евгений Крохалев, Екатерина Васильева
Источник задачи: Седьмое открытое личное первенство УрГУ по спортивному программированию - 25 февраля 2006 года
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1434. Автобусы города Васюки