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

Соревнование команд УрГУ. Март 2002

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

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

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

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

Первая строка содержит два вещественных числа: скорость ходьбы и скорость перемещения с помощью метро. Скорости лежат в пределах от 0.5 до 10000. Вторая скорость всегда не меньше первой.
Затем следует описание метро. В первой строке описания находится целое число N — количество станций метро (2 ≤ N ≤ 200). Следующие N строк содержат по два вещественных числа каждая (i-я строка содержит координаты i-й станции). Затем следует описание соединений между станциями. Каждое соединение определяется парой целых чисел — номерами соединённых станций. Соединения в списке не повторяются. Общее количество соединений не превышает 400. Список соединений завершает пара нулей.
Можно считать, что станции соединяются по прямой, так что время перемещения между станциями равно расстоянию между ними, делённому на скорость перемещения с помощью метро. Перемещаться между станциями можно в любую сторону. Время перемещения пешком между двумя точками равно расстоянию между ними, делённому на скорость ходьбы.
Отметим, что вход и выход из метро, а также смена поезда возможны только на станциях и не требуют дополнительного времени.
Последними даны координаты точек 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
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1205. На метро или пешком?