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

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

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

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

Формат входного файла 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.

13.1.4. Задача «На болоте» (алгоритм Флойда)

Так как жестких временных ограничений не было, то многие участники решили эту задачу методом Флойда. Повторимся, что этот метод прост и легок в запоминании, но будет искать кратчайшие пути между всеми вершинами. Приведем программу Антона Александрова (Самарский лицей информационных технологий). Программа написана в консольном приложении Delphi.

program Project1;

{$APPTYPE CONSOLE}

uses SysUtils;

var

i, n, t, k, j: integer;

ar: array [1.. 500, 1.. 500] of real;

Begin

{ TODO -oUser -cConsole Main: Insert code here }

Assignfile (input, 'input.txt'); Reset (input);

Assignfile (output, 'output.txt'); Rewrite (output);

Readln (n);

For i:= 1 to n do

For t:= 1 to n do

ar [i, t]:= high (integer); {макс. целое}

For i:= 1 to n do Begin

Repeat

Read (t);

If t > 0 then Begin

   Read (ar [i, t]);

   ar [t, i]:= ar [i, t];

End;

Until t = 0;

Readln;

End;

For k:= 1 to n do Begin

For i:= 1 to n - 1 do

For j:= i + 1 to n do

   If ar [i, j] > ar [i, k] + ar [k, j] then

   Begin

     ar [i, j]:= ar [i, k] + ar [k, j];

     ar [j, i]:= ar [i, j];

   End;

End;

Write (ar [1, n]: 0: 2);

Closefile (input); Closefile (output);

End.

Задачи с сайта ACM.TIMUS.RU

Зарегистрируйтесь на сайте и запишете выделенный вам код. При работе с сайтом текстовые файлы не описываются и не назначаются. Нельзя подключать модули (даже привычный Uses Crt;) использовать операторы вида Write(‘Введите число’). Следует убирать и поставленный во время отладки в конце программы оператор Readln.

Сдайте задачу «А+В» (номер на сайте 1000)-там все числа целые. Достаточно написать:

Var a, b: integer;

Begin

Read(a, b);

Write(a+b);

End.

Успехов!