#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>

// структура "точка"
struct Scoord
{
 double x;
 double y;
};

const int LMAX=0, RMAX=30, TMAX=24, BMAX=0;

int N;


double Smin;  // сюда запишем минимальную сумму
int *minPath;  // здесь будет минимальный путь
double **matr;  // матрица, где будем хранить длины ребер
Scoord *mas;  // массив точек

// рекурсивная функция для поиска пути.
// принимает указатель на текущий путь (который формируется с каждым вызовом)
// порядковый номер текущей вершины и текущую сумму ребер
void getMinPath(int *tekPath, int tek, double tekS)
{

if(tek==N)  // если перебрали все вершины
 {
  if(tekS<Smin || Smin==0)  // и если текущая сумма меньше той, которую запомнили
   {
    Smin = tekS;  // запоминаем
    for(int j=0; j<N; j++)
     minPath[j] = tekPath[j];  // и запоминаем путь
   }
  return;
 }
 // иначе...
 bool b;
 for(int i=0; i<N; i++)  // перебираем все вершины
 {
  b = false;  
  for(int j=0; j<tek; j++)  // смотрим, нет ли текущей вершины в уже сформировавшемся пути
   if(tekPath[j]==i) b=true;  // если есть, ставим флаг
  if(b) continue;  // если флаг установлен, пропускаем вершину и берем следующую

 tekPath[tek] = i;  // добавляем вершину к пути

 getMinPath(tekPath, tek+1, tekS+matr[tekPath[tek-1]][i]);  // и ищем следующую вершину

 }

}
//-----------

// функция для заполнения матрицы
// принимает указатель на матрицу
void fillMatr(double **matr)
{
 int i,j;
 double dlina;
 for(i=0;i<N;i++)
  for(j=0;j<N;j++)
   if(j==i) continue; 
   else
    {  // для двух разных вершин считаем длину ребра
     dlina = sqrt(pow(mas[i].x-mas[j].x,2)+pow(mas[i].y-mas[j].y,2));
     if(dlina<matr[i][j] || matr[i][j]==0)
      matr[i][j] = dlina;
    }
}
//----------------------


int main()
{
int i,j;
int *tekPath;

srand(time(NULL));
printf("Vvedite kolichestvo vershyn: ");
scanf("%d",&N);

// выделяем память под массив вершин
mas = new Scoord[N];
for(i=0;i<N;i++)
 {
  //  разбрасываем точки
  mas[i].x = rand()*(RMAX-LMAX)/(double)RAND_MAX+LMAX;
  mas[i].y = rand()*(BMAX-TMAX)/(double)RAND_MAX+TMAX;
  printf("To4ka %d: %5.3lf  %5.3lf\n",i,mas[i].x,mas[i].y);
 }
printf("\n");
//==================
// выделяем память под матрицу
matr = new double*[N];
for(i=0;i<N;i++)
 matr[i] = new double[N];


// память под минимальный и текущий пути
tekPath = new int[N];
minPath = new int[N];

Smin = 0;
for(i=0; i<N;i++)
 for(j=0;j<N;j++)
  matr[i][j] = 0;
fillMatr(matr);  // заполняем матрицу

// ищем минимальный путь
for(i=0; i<N; i++)  // в цикле перебираем стартовые вершины
 {
  tekPath[0] = i;
  getMinPath(tekPath, 1, 0);
 }

printf("\n Minimalnaya summa = %5.3lf\n\n",Smin);

printf("derevo:\n");
printf("%d",minPath[0]);
for(i=1;i<N;i++)
 printf(" -> %d",minPath[i]);
printf("\n");


for(i=0;i<N;i++)
 delete[] matr[i];
delete[] matr;
delete mas;

delete[] minPath;
delete[] tekPath;

getch();
return 0;
}