Задача «На болоте» (алгоритм Дейкстры)

Автор задачи: Рогачева Е.В.

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

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

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

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

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

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

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

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

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

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

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

3 5.10

2 4.6 3 5.1 0 0

0 0

0 0

Приведем решение автора задачи.

Const

NMax = 500;

QMin = 0.001;

QMax = 1000;

WayMax = (NMax*NMax+1)*QMax;

{это число будет служить заменой "бесконечно большого" в}

{алгоритме Дейкстры. Разумеется, возможны и другие варианты}

Type

T_Incidence_Vector = array[1..NMax] of real;

T_Incidence_Matrix = array[1..NMax] of T_Incidence_Vector;

T_Hillok = array[1..NMax] of boolean;

T_Hillok_Way = array[1..NMax] of real;

Var

fin, fout: TextFile;

IM: T_Incidence_Matrix;

S: real;

N: integer;

Procedure ReadData;

Var

P, j: integer;

Q: real;

Begin

AssignFile(fin, 'input.txt'); Reset(fin);

Readln(fin, N);

{сначала заполним матрицу }

For j := 1 to N-1 do Begin

Read(fin, P, Q);

While not((P = 0) and (Q < QMin)) do

Begin

IM[j, P] := Q;

IM[P, j] := Q; {так как граф неориентированный,}

{и матрица симметрична}

Read(fin, P, Q);

End;

Readln(fin);

End;

{последнюю строчку на всякий случай обработаем}

{отдельно - хотя в ней, если}

{следовать условию задачи, должно быть только 0 0}

Read(fin, P, Q);

While not((P = 0) and (Q < QMin)) do Begin

IM[N, P] := Q;

IM[P, N] := Q;

read(fin, P, Q);

End;

CloseFile(fin);

End;

Function min(a, b: real): real;

Begin

If a < b then result := a

else result := b;

End;

Function MinInHillokWay(const h: T_Hillok; const hw: T_Hillok_Way;

out minNum: integer): real;

Var

i, j: integer;

Begin

{ищем первую кочку вне множества; кочка № 1 в}

{него заведомо входит.}

{проверка того, что хотя бы одна кочка еще}

{есть, здесь не проводится - это задача основного цикла}

{процедуры Solution}

i := 2;

While h[i] do i := i+1;

{найденную принимаем за "потенциальный минимум"}

result := hw[i];

minNum := i;

{а теперь просматриваем оставшиеся кочки и, если найдется что-то более подходящее, обновляем значение минимума}

For j := i+1 to N do Begin

If (not(h[j])and (hw[j] < result))

then Begin

result := hw[j];

minNum := j;

End;

End;

End;

Procedure Solution;

Var

h: T_Hillok; {множество кочек, которые уже}

{ используются в маршрутах}

hw: T_Hillok_Way; {уже имеющиеся длины}

{ маршрутов от первой до других кочек}

i, k: integer;

add_hillok: integer;

to_hillok: real;

Begin

For i := 1 to N do h[i] := false;

h[1] := true;

For i := 1 to N do hw[i] := WayMax;

hw[1] := 0.0;

{первую итерацию алгоритма Дейкстры выполним отдельно}

For i := 2 to N do Begin

{если до кочки существует прямой путь из первой}

If (IM[1, i] > 0) then hw[i] := IM[1, i];

End;

{а теперь анализируем кочки до тех пор,}

{пока множество не рассмотренных не опустеет}

{Поскольку может оказаться, что просмотреть надо все}

{вершины, можно просто пустить цикл от 1 до N}

For k := 1 to N do Begin

{находим кочку, которая ближе всего к первой }

{кочке, но еще не входит в множество h}

to_hillok := MinInHillokWay(h, hw, add_hillok);

{и добавляем ее к множеству h}

h[add_hillok] := true;

If add_hillok = N {если встретили кочку N, }

then break; {дальше можно не считать}

{теперь расстояния до остальных надо пересчитать

{с учетом этой кочки как промежуточной}

For i := 1 to N do Begin

{если кочка еще не входит в множество уже рассмотренных и

до нее существует прямой путь из вновь добавленной}

If (not(h[i]) and (IM[add_hillok, i] > 0))

then hw[i] := min(hw[i], to_hillok+IM[add_hillok, i])

{ to_hillok == hw[add_hillok], просто чтобы не}

{обращаться по многу раз к массиву }

End; {for i}

End; {while}

{теперь осталось просто забрать значение из массива hw}

S:= hw[N];

End; {Solution}

Procedure WriteData;

Begin

AssignFile (fout, 'output.txt'); Rewrite (fout);

Write (fout, S:0:2);

CloseFile (fout);

End;

Begin

ReadData;

Solution;

WriteData;

End.