Трудные маршруты
В рамках подготовки к предстоящим Олимпийским играм вас попросили разработать велосипедные тренировочные маршруты для команды вашей страны. Тренировочный комитет хочет определить маршруты для поездок между парами мест в различных регионах страны. Каждый маршрут должен соответствовать заданному уровню сложности, который определяется крутизной его холмов.
Вам будет предоставлена карта дорог с данными о высоте. Каждое пересечение, где встречаются две или более дорог, определяется его x-, y- и z-координатами. Каждая дорога начинается и заканчивается на пересечении, является прямой и не содержит мостов или туннелей. Уровень сложности, d, для езды на велосипеде по дороге равен 0, если дорога ровная или идет вниз по склону. Сложность дороги при движении вверх по склону равна 100*подъем/пробег. Здесь подъем — это абсолютное изменение высоты, а пробег — это расстояние между двумя точками пересечения в его горизонтальной проекции на 2D-плоскость на уровне нуля. Обратите внимание, что уровень сложности для спуска равен нулю.
Маршрут, представляющий собой последовательность дорог, где следующая дорога начинается там, где заканчивается предыдущая, имеет уровень сложности d, если максимальный уровень сложности среди всех его дорог равен d. Комитет также заинтересован в том, чтобы выбранный маршрут между двумя местами, если такой маршрут с заданным уровнем сложности существует, был с наименьшим возможным расстоянием.
Напоминание: Функция округления X означает X, усеченное до целого числа.
На рисунке показана карта дорог с тремя пересечениями для трех примеров ввода.
Метки на краях более темной поверхности указывают уровень сложности подъема в гору. Более светлая поверхность — это горизонтальная проекция на 2D-плоскость на уровне нуля.
Входные данные
Ввод состоит из множества карт дорог. Описание каждой карты начинается с двух неотрицательных целых чисел N и M, разделенных пробелом на отдельной строке, которые представляют количество пересечений и количество дорог соответственно. 0 < N, M ≤ 10000. Значение обоих N и M, равное нулю, обозначает конец входных данных.
Каждая из следующих N строк содержит три целых числа, разделенных пробелами, которые представляют x-, y- и z-координаты пересечения. Целые числа имеют значения от 0 до 10000 включительно. Пересечения нумеруются в порядке их появления, начиная с единицы. Каждая из следующих M строк содержит два целых числа, которые представляют начальное и конечное пересечения дороги.
Наконец, три целых числа s, t и d, которые представляют желаемый номер начального пересечения s, номер конечного пересечения t и уровень сложности d для тренировочного маршрута, даны на отдельной строке. Действительный тренировочный маршрут должен иметь хотя бы одну дорогу с уровнем сложности d и ни одной дороги с уровнем сложности больше, чем d. 0 ≤ d ≤ 10. Если тренировочный маршрут должен образовать замкнутый круг, то s и t — это одинаковые номера пересечений.
Выходные данные
Для каждой карты дорог и желаемого маршрута вывод состоит из одной строки, содержащей:
число, обозначающее кратчайшую длину тренировочного маршрута, округленное до одного десятичного знака, или
единственное слово "None", если подходящий маршрут не существует.
Напоминание: Округление положительного числа R.xxxy до трех десятичных знаков
Если четвертый десятичный знак меньше 5, то округленное значение — R.xxx
В противном случае округленное значение — R.xxx + 0.001
Примеры: для значения 10.3463 вывод должен быть 10.346, а для значения 10.3695 вывод — либо 10.37, либо 10.370