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

1205. На метро или пешком?

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Представьте себя в большом городе. Вы хотите попасть из точки A в точку B. Для этого вы можете идти пешком или использовать метро. Перемещение с помощью метро быстрее, но входить в метро и выходить из него можно только на станциях. Чтобы сэкономить время, вы решили написать программу нахождения самого быстрого пути.

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

Первая строка содержит два вещественных числа: скорость ходьбы и скорость перемещения с помощью метро. Вторая скорость всегда больше первой.
Затем следует описание метро. В первой строке описания находится целое число N — количество станций метро. Можете считать, что N не превосходит 200. Следующие N строк содержат по два вещественных числа каждая (i-я строка содержит координаты i-й станции). Затем следует описание соединений между станциями. Каждое соединение определяется парой целых чисел — номерами соединённых станций. Список соединений завершает пара нулей. Будем считать, что станции соединяются по прямой, так что время перемещения между станциями равно расстоянию между станциями, делённому на скорость перемещения с помощью метро.
Заметим, что вход и выход из метро, а также смена поезда возможны только на станциях и не требуют дополнительного времени.
Последними даны координаты точек A и B по паре координат в строке.

Результат

Первая строка должна содержать минимальное время, необходимое, чтобы попасть из точки A в точку B. Время должно быть выведено с точностью 10−6. Вторая строка описывает использование метро при передвижении. Она начинается количеством станций, которые нужно посетить, затем следует список номеров станций в порядке, в котором их нужно посетить.

Пример

исходные данныерезультат
1 100
4
0 0
1 0
9 0
9 9
1 2
1 3
2 4
0 0
10 10
10 0
2.6346295
4 4 2 1 3
Автор задачи: Александр Клепинин
Источник задачи: Соревнование команд УрГУ, март 2002