Зимняя школа в "Эврике"

Но помимо нахождения наименьшей стоимости маршрута, разумеется, хотелось бы найти и сам маршрут минимальной  стоимости.
Такая задача называется задачей «восстановления ответа». 

Для восстановления ответа будем для каждой точки i запоминать номер точки Prev[i], из которой кузнечик попал в точку i, 
если он будет передвигаться по пути минимальной стоимости. 
То есть Prev[i] — это точка, предшествующая точке с номером i на пути минимальной стоимости (также говорят, что Prev — 
это массив предшественников). 
Как определить Prev[i]? 
Если C[i − 1] < C[i − 2], то кузнечик попал в точку i из точки i - 1, поэтому Prev[i] = i - 1, 
иначе Prev[i] = i - 2. 
Модифицируем алгоритмы вычисления значений целевой функции, одновременно вычисляя значения Prev[i].

Пример программы на языке Python:

C = [0] * (n + 1)
C[1] = Price[1]
Prev[1] = 0
for i in range(2, n + 1):
    if C[i — 1] < C[i — 2]:
        C[i] = C[i — 1] + Price[i]
        Prev[i] = i — 1
    else:
        C[i] = C[i — 2] + Price[i]
        Prev[i] = i — 2


Пример программы на языке Pascal:

var
  C, Price, Prev: array[0..100] of longint;
  j, i, n: longint;
begin
  readln(n);
  for i := 1 to n do
    read(Price[i]);
  for i := 0 to n do
    C[i] := 0;
  C[1] := Price[1];
  Prev[1] := 0;
  for i := 2 to n do
    if C[i - 1] < C[i - 2] then begin
      C[i] := C[i - 1] + Price[i];
      Prev[i] := i - 1;
    end else begin
      C[i] := C[i - 2] + Price[i];
      Prev[i] := i - 2;
    end;
end.
 

Теперь для восстановления пути необходимо начать с точки n и переходить от каждой точки к ее предшественнику, пока путь 
не дойдет до начальной точки с номером 0. 
Номера всех вершин будем добавлять в список (массив) Path.

Пример программы на языке Python:

Path = []
i = n
while i > 0:
    Path.append(i)
    i = Prev[i]
Path.append(0)
Path = Path[::-1]


Пример программы на языке Pascal:
  i := n;
  j := 1;
  while i > 0 do 
  begin
    Path[j] := i;
    i := Prev[i];
    inc(j);
  end;
  Path[j] := 0;
  for i := j downto 1 do
    write(Path[i], ' '); 
 

В конце в список Path добавляется начальная вершина номер 0, которая не была обработана в основном цикле, а затем весь 
список Path разворачивается в обратном порядке (т. к. вершины добавляются в обратном порядке, от конечной к начальной).

Но можно обойтись и без списка Prev. 
Мы в любой момент можем определить, из какой точки кузнечик пришел в точку i, если сравним C[i - 1] и C[i - 2]. 
Поэтому решение о том, к какой вершине переходить при восстановлении ответа можно принимать непосредственно при
восстановлении ответа, сравнив C[i - 1] и C[i - 2]. 
Путь восстанавливается через ту вершину, для которой значение C будет меньше.

Пример программы на языке Python

Path = []
i = n
while i > 0:
    if C[i — 1] < C[i — 2]:
        prev = i — 1
    else:
        prev = i - 2
    Path.append(prev)
    i = prev
Path.append(0)
Path = Path[::-1]
 
Пример программы на языке Pascal:

var
  C, Price, Path: array[-1..100] of longint;
  j, i, n, prev: longint;
begin
  readln(n);
  for i := 1 to n do
    read(Price[i]);
  for i := 1 to n do
    C[i] := 0;
  C[-1] := -1;  
  C[0] := 0;
  C[1] := Price[1];
  for i := 2 to n do
    C[i] := min(C[i - 1], C[i - 2]) + Price[i];
  i := n;
  j := 1;
  Path[j] := i;
  while i > 0 do 
  begin
    inc(j);
    if C[i - 1] < C[i - 2] then
      prev := i - 1
    else
      prev := i - 2;
    Path[j] := prev;
    i := prev;
  end;
  Path[j] := 0;
  for i := j downto 1 do
    write(Path[i], ' '); 
end.