Складні маршрути#3046

Складні маршрути

2 секунди

32 мегабайти

Складна

На честь прийдешньої Олімпіади вас запросили запропонувати велосипедні тренувальні маршрути для команди вашої країни. Тренувальний комітет прагне визначити маршрути між парами точок у різних місцях країни. Кожен маршрут повинен мати заданий рівень складності, що ґрунтується на крутизні його схилів.

Вам буде надано дорожню карту з даними про висоти. Кожне перехрестя, де перетинаються два чи більше шляхів, визначається своїми $x$ -, $y$ - та $z$ -координатами. Кожна дорога починається і закінчується на перехресті, є прямою та не перетинає інші дороги (тобто без мостів і тунелів). Рівень складності $d$ для проїзду по дорозі дорівнює $0$ , якщо дорога рівна або подолана у напрямку вниз. Для підйому (нерівної дороги), складність визначається як $100 \cdot rise / run$ 100 \cdot \text{rise}/\text{run}, де $rise$ — абсолютна зміна висоти, а $run$ — відстань між двома перехрестями у горизонтальній проекції на площину $z = 0$ z=0. Зауважте: складність при спуску завжди дорівнює нулю.

Маршрут — це послідовність доріг, де наступна дорога починається від перехрестя, у якому завершилася попередня. Маршрут має рівень складності $d$ , якщо максимальна складність серед усіх його доріг дорівнює $d$ . Комітет також бажає, якщо між двома заданими точками існує маршрут із заданим рівнем складності, отримати маршрут із можливо найменшою загальною довжиною.

Нагадування: Функція підлоги $X$ означає перетворення $X$ до цілого числа відкиданням дробової частини.

Вхідні дані

Вхід містить кілька дорожніх карт. Опис кожної карти починається з двох невід'ємних цілих чисел $N$ та $M$ (розділених пробілом, кожне окремим рядком), які задають кількість перехресть і доріг відповідно ( $0 < N, M \leq 10000$ 0 < N, M \leq 10000). Рядок із $N = 0$ N = 0 та $M = 0$ M = 0 означає кінець введення.

Кожен із наступних $N$ рядків містить по три цілі числа, розділених пробілами, що відповідають $x$ -, $y$ - та $z$ -координатам перехрестя ( $0 \leq x, y, z \leq 10000$ 0 \leq x, y, z \leq 10000). Перехрестя нумеруються у порядку появи, починаючи з одиниці. Далі йдуть $M$ рядків, кожен з яких містить два цілі числа — номери перехресть, між якими пролягає дорога.

Нарешті, три цілі числа $s$ , $t$ , $d$ задають початкове перехрестя $s$ , кінцеве перехрестя $t$ та шуканий рівень складності маршруту $d$ ( $0 \leq d \leq 10$ 0 \leq d \leq 10). Дійсний тренувальний маршрут повинен містити принаймні одну дорогу з рівнем складності $d$ і жодної дороги з рівнем складності, що перевищує $d$ . Якщо потрібен замкнутий маршрут, то $s$ та $t$ вказують на одне і те саме перехрестя.

Вихідні дані

Для кожної карти доріг і запитаного маршруту виведіть в окремому рядку:

довжину найкоротшого дійсного тренувального маршруту, округлену до однієї десяткової, або
слово None, якщо такого маршруту не існує.

Нагадування: Округлення додатного числа $R . xxx y$ до трьох знаків після десяткової

Якщо четверта цифра після десяткової менша за $5$ , округлене значення — це $R . xxx$
Інакше — $R . xxx + 0.001$ R.xxx + 0.001

Приклади: для $10.3463$ результат має бути $10.346$ ; для $10.3695$ допустимі як $10.37$ , так і $10.370$ .

Приклади

Приклад 1