{
	Дана матрица расстояний между населёнными пунктами.
	Решить задачу коммивояжера, т.е. построить маршрут, проходящий через все пункты и возвращающий в начальный,
	при котором суммарное расстояние минимально.
0 3 93 13 33 9 57
4 0 77 42 21 16 34
45 17 0 36 16 28 25
39 90 80 0 56 7 91
28 46 88 33 0 25 57
3 88 18 46 92 0 7
44 26 33 27 84 39 0
}
uses
	crt;

const
	N = 7;
	C: array [1..N, 1..N] of byte = (
	( 0,  3, 93, 13, 33,  9, 57),
	( 4,  0, 77, 42, 21, 16, 34),
	(45, 17,  0, 36, 16, 28, 25),
	(39, 90, 80,  0, 56,  7, 91),
	(28, 46, 88, 33,  0, 25, 57),
	( 3, 88, 18, 46, 92,  0,  7),
	(44, 26, 33, 27, 84, 39,  0)); {Матрица расстояний}

label
	Out; {Метка для завершающих операций}

var
	Tour, P: array [1..N] of word; {Оптимальный и текущие туры}
	l, s: word; {протяженность тура}
	i, j, k, min, ind: byte; {счетчики и индексы}
	All: boolean; {Признак окончания перебора}

{Программа решения задачи коммивояжера методом лексического перебора.}
begin
	clrscr;
	{Инициализация}
	All := false; {Перебраны не все варианты}
	l := MaxInt; {Оптимальный тур неизвестен}
	for i := 1 to N do
		P[i] := i; {Строим первый тур}
	repeat {Вычисляем его длину}
		s := 0;
		for i := 1 to (N - 1) do
			s := s + C[P[i], P[i+1]];
		s := s + C[P[n], P[1]];
		{Полагаем первый тур текущим}
		if (l > s) then begin
			Tour := P;
			l := s;
		end;
	
		{Генерируем все (N-1)! перестановок}
		for i := N downto 3 do begin
			if (P[i] < P[i-1]) then
				continue;
			min := N + 1;
			k := P[i-1];
		{Ищем миним. число из тех, что больше k и правее}
		for j:=i to N do
			if (P[j] > k) and (P[j] < min) then begin
				min := P[j];
				ind:=j;
			end;
		{Рокировка min и k}
		P[i-1] := min;
		P[ind] := k;
	
		{Элементы на местах от i до N упорядочиваем по возрастанию}
		for j := i to (N - 1) do begin
			min := N + 1;
			for k := j to N do 
				if (min > P[k]) then begin
					min := P[k];
					ind := k;
				end;
			k := P[j];
			P[j] := min;
			P[ind] := k;
		end;
		GoTo Out;
	end;
	{Проверяем перебраны ли все перестановки}
	All:=true;
Out:
	Until All;
	{Если перебраны все перестановки, то выдаем оптимальный тур}
	write('Minimum tour: ');
	for i:=1 to N do write(Tour[i], '-');
	write('1');
	writeLn(' length is ', l);
	writeln('Done. Press any key...');
	readkey;
end.