{
	написать программу на базе общей схемы алгоритма поиска с возвратом
	Найти кратчайший путь на графе от вершины 1 до вершины 35.
	Индекс - вершина источник.
	m,n; - данные для приемника, где m - вершина, n - расстояние.
}
uses
	crt; {Используем стандартный модуль Crt}

type
	TNode = record
		name: string;
		index,
		dfp: byte; {distance from parent}
	end;

const
	Dist: array[1..34] of string = ({массив переходов и их стоимости; индекс элемента узел-источник.}
{ 1}	'2,0;3,0;4,0;5,0;6,0;7,0;',
{ 2}	'8,10;9,13;',
{ 3}	'9,8;10,10;11,12;',
{ 4}	'10,7;11,8;',
{ 5}	'11,5;12;8;',
{ 6}	'12,3;13,5;14,7;',
{ 7}	'13,2;14,3;',
{ 8}	'15,13;16,12;',
{ 9}	'16,8;',
{10}	'16,8;17,8;18,15;',
{11}	'17,13;18,8;19,7;',
{12}	'19,3;',
{13}	'19,3;20,3;21,4;',
{14}	'21,4;', 
{15}	'22,9;', 
{16}	'22,10;23,10;', 
{17}	'22,9;23,15;24,11;25,14;', 
{18}	'25,4;', 
{19}	'25,5;26,5;', 
{20}	'25,4;26,7;27,6;28,9;', 
{21}	'28,8;', 
{22}	'29,10;', 
{23}	'29,11;30,15;', 
{24}	'29,13;30,14;', 
{25}	'30,14;31,10;', 
{26}	'32,6;33,4;', 
{27}	'32,8;33,9;', 
{28}	'33,9;34,5;', 
{29}	'35,0;', 
{30}	'35,0;', 
{31}	'35,0;', 
{32}	'35,0;', 
{33}	'35,0;', 
{34}	'35,0;');

var
	node: TNode; {элемент узел}
	candidat, vector: string; {предполагаемая и кратчайшая последовательности}
	S: byte; {стоимость кратчайшего пути}

procedure next(var st: string; var node:TNode); {получение следующего узла}
var
   data, name: string; {узел назначения и стоимость, имя узла в строковом виде}
   dist, code: integer; {стоимость перехода (расстояние), код преобразования строки в число}
   posch: byte; {позиция символа-разделителя}
begin
   posch := pos(';', st); {ищем вхождение разделителя узлов}
   data := copy(st, 1, posch-1); {копируем данные по узлу и стоимости}
   delete(st, 1, posch); {удаляем эти данные вместе с разделителем}
   posch := pos(',', data); {ищем вхождение разделителя данных по узлу}
   name := copy(data, 1, posch-1); {имя узла забираем}
   delete(data, 1, posch); {и удаляем}
   node.name := name; {запоминаем имя в структуре для доступа извне}
   val(name, node.index, code); {получаем номер узля назначения}
   val(data, node.dfp, code); {и расстояние до него}
end;


procedure solve(path:string; candidat:byte; child:byte); {поиск решения}
{формальные параметры: найденный путь, стоимость пути, рассматриваемый узел}
var
	nodes: string; {последовательность узлов назначения}
begin
	if (child = 35) then begin {если достигнут конечный узел назначения}
		if (candidat < S) then begin {найденный путь меньше эталонного наименьшего? да}
			S := candidat; {сохраним длину пути}
			vector := path; {и последовательность переходов}
		end;
	end else begin {иначе}
		nodes := Dist[child]; {достанем список узлов назначения из массива переходов}
		while (nodes > '') do begin {пока не просмотрены все варианты переходов}
			next(nodes, node); {получим очередной узел назначения}
			if ((candidat + node.dfp) < S) then {если уже найденный путь не превышает эталонного}
				solve(path + '>' + node.name, candidat + node.dfp, node.index); {поищем варианты для этого узла}
		end;
	end;
end;

begin
	clrscr; {очистка экрана}
	S := 255; {установим первоначальную эталонную стоимость заведомо большей любого из путей}
	solve('1', 0, 1); {будем рассматривать все подходяшие варианты начиная с первой вершины}
	writeln('Shortest path (', S, '): ', vector); {вывод информации о найденном кратчайшем пути}
	writeln('Done. Press any key...'); {сообщаем, что работа завершена}
	readkey; {ждем нажатия клавиши пользователем}
end.