Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

На болоте

Задачу добавил: alef

Успешно сдано решений: 106

Добрался Иван-царевич до болот, тут они с волком и простились. Пригляделся Иван-царевич, и стрелу свою увидел: торчит она в самой дальней кочке. Ну что ж, делать нечего, придется прыгать с кочки на кочку, чтобы до нее добраться.

Ваша задача - определить наиболее короткий маршрут до стрелы.

Формат входного файла input.txt

Первая строка - целое число N (1 <= N <= 500) - количество кочек на болоте.

Далее следуют N строк, описывающие кочки. Строка № j+1 (j = 1, 2, …, N) содержит 0 или более пар, состоящих из целого числа Pk (1 <= Pk <= N, j < k < N) и вещественного числа Qk (0,001 <= Qk <= 1000, j < k < N) через пробел (пары также разделены пробелами). Целое число Pk (первое в паре) - номер кочки, вещественное число Qk - расстояние от кочки № j до кочки № Pk. Каждая из N строк завершается парой 0 0.

При этом первая строка описывает кочку, на которую Иван-царевич встает первой, а последняя - кочку, до которой и нужно добраться.

Обратите внимание, что во входном файле указаны расстояния только между такими парами кочек № j и № Pk, в которых j < Pk. Расстояние от кочки № Pk до кочки № j в точности равно расстоянию от кочки № j до кочки № Pk. Гарантируется, что путь от кочки № 1 до кочки № N всегда существует.

Примечание. Поскольку Иван-царевич может прыгнуть не далее определенного расстояния, во входном файле указаны только принципиально достижимые для него кочки, когда он стоит на кочке №j.

Формат выходного файла output.txt

Первая строка - вещественное число S с точностью до 2 знаков после запятой - минимальное расстояние, которое придется преодолеть Ивану-царевичу, добираясь до стрелы.

Пример входного файла

3

2 4.6 3 5.1 0 0

0 0

0 0

Пример выходного файла.

5.10

Сдать задачу

Задать вопрос жюри по этой задаче