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

#define VERY_LARGE 1000000000

void genrand ( int *x, int *y, int **d, int n )
{
   int i, j, t;

   for (i=0; i<n; ++i) {
      x[i] = rand() % 1000;
      y[i] = rand() % 1000;
      d[i][i] = 0;
   }
   for (i=n-2; i>=0; --i) {
      for (j=0; j<=i; ++j) {
         if (x[j] > x[j+1]) {
            t = x[j]; x[j] = x[j+1]; x[j+1] = t;
         }
      }
   }

   /**** For reproducing the sample ****
   x[0] = 21; x[1] = 36; x[2] = 59; x[3] = 87; x[4] = 193; x[5] = 286;
   x[6] = 561; x[7] = 737; x[8] = 821; x[9] = 856; x[10] = 958; x[11] = 962;
   y[0] = 993; y[1] = 490; y[2] = 101; y[3] = 740; y[4] = 997; y[5] = 19;
   y[6] = 131; y[7] = 100; y[8] = 614; y[9] = 246; y[10] = 136; y[11] = 967;
   ****/
   for (i=0; i<n; ++i) printf("(%3d,%3d) ",x[i],y[i]);
   printf("\n");
   for (i=1; i<n; ++i) for (j=0; j<i; ++j) {
      d[i][j] = (int)sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
      d[j][i] = d[i][j];
   }
}

int permutation ( int *p, int n, int k, int **d, int bestcost, int *pp )
{
   int i, t, thiscost;

   if (k == n) {
      thiscost = d[p[n-1]][p[0]];
      for (i=0; i<=n-2; ++i) thiscost += d[p[i]][p[i+1]];
      if (thiscost < bestcost) {
         bestcost = thiscost;
         for (i=0; i<=n-1; ++i) pp[i] = p[i];
      }
   } else {
      for (i=k; i<n; ++i) {
         t = p[k]; p[k] = p[i]; p[i] = t;
         bestcost = permutation(p,n,k+1,d,bestcost,pp);
         t = p[k]; p[k] = p[i]; p[i] = t;
      }
   }
   return bestcost;
}

int exactTSP ( int **d, int n )
{
   int *p, *pp, i, bestcost;
   p = (int *)malloc(n*sizeof(int));
   for (i=0; i<n; ++i) p[i] = i;
   pp = (int *)malloc(n*sizeof(int));
   bestcost = permutation(p,n,1,d,VERY_LARGE,pp);
   for (i=0; i<n; ++i) printf("%d%c",pp[i],(i==n-1)?'.':'-');
   free(p); free(pp);
   return bestcost;
}

void recgenpath ( int *p, int L, int R, int **d )
{
   int i, j, k, M, *pp, nexti, nextj;
   int besti, bestj, bestnexti, bestnextj, bestcost, thiscost;

   if (R <= L+2) return;
   M = (L + R) / 2;
   recgenpath(p,L,M,d); recgenpath(p,M+1,R,d);
   bestcost = VERY_LARGE;
   for (i=L; i<=M; ++i) for (j=M+1; j<=R; ++j) {
      nexti = (i == M) ? L : i+1;
      nextj = (j == R) ? M+1 : j+1;
      thiscost = d[p[i]][p[nextj]] + d[p[j]][p[nexti]]
                 - d[p[i]][p[nexti]] - d[p[j]][p[nextj]];
      if (thiscost < bestcost) {
         bestcost = thiscost;
         besti = i; bestj = j;
         bestnexti = nexti; bestnextj = nextj;
      }
   }
   pp = (int *)malloc((R-L+1)*sizeof(int));
   k = 0;
   for (i=L; i<=besti; ++i) pp[k++] = p[i];
   j = bestnextj; pp[k++] = p[j];
   while (j != bestj) {
      if (j == R) j = M+1; else ++j;
      pp[k++] = p[j];
   }
   if (bestnexti != L) for (i=bestnexti; i<=M; ++i) pp[k++] = p[i];
   for (i=L; i<=R; ++i) p[i] = pp[i-L];
   free(pp);
}

int dncTSP ( int **d, int n )
{
   int *p, i, bestcost;
   p = (int *)malloc(n*sizeof(int));
   for (i=0; i<n; ++i) p[i] = i;
   recgenpath(p,0,n-1,d);
   for (i=0; i<n; ++i) printf("%d%c",p[i],(i==n-1)?'.':'-');
   bestcost = d[p[n-1]][p[0]];
   for (i=0; i<=n-2; ++i) bestcost += d[p[i]][p[i+1]];
   free(p);
   return bestcost;
}

int greedyTSP ( int **d, int n )
{
   int *p, *visited, k, i, j, nexti;
   int bestcost, mindist, thisdist, nearesti, nearestj;
   p = (int *)malloc(n*sizeof(int));
   visited = (int *)malloc(n*sizeof(int));
   for (i=0; i<n; ++i) visited[i] = 0;
   k = 0; p[k++] = 0; visited[0] = 1;
   while (k < n) {
      mindist = VERY_LARGE;
      for (i=0; i<k; ++i) {
         nexti = (i==k-1) ? 0 : i+1;
         for (j=0; j<n; ++j) if (!visited[j]) {
            thisdist = d[p[i]][j] + d[j][p[nexti]] - d[p[i]][p[nexti]];
            if (thisdist < mindist) {
               mindist = thisdist;
               nearesti = i;
               nearestj = j;
            }
         }
      }
      for (i=k-1; i>=nearesti+1; --i) p[i+1] = p[i];
      p[nearesti+1] = nearestj;
      ++k; visited[nearestj] = 1;
   }
   for (i=0; i<n; ++i) printf("%d%c",p[i],(i==n-1)?'.':'-');
   bestcost = d[p[n-1]][p[0]];
   for (i=0; i<=n-2; ++i) bestcost += d[p[i]][p[i+1]];
   free(p); free(visited);
   return bestcost;
}

int dpTSP ( int **d, int n )
{
   int *p, **best, **last, i, j, t, u, v, thiscost, bestcost, bestlast;
   best = (int **)malloc((1 << (n-1)) * sizeof(int *));
   last = (int **)malloc((1 << (n-1)) * sizeof(int *));
   for (i=0; i<(1<<(n-1)); ++i) {
      best[i] = (int *)malloc(n*sizeof(int));
      last[i] = (int *)malloc(n*sizeof(int));
   }
   best[0][0] = 0; last[0][0] = -1;
   for (j=1; j<n; ++j) {
      best[0][j] = d[0][j]; last[0][j] = 0;
   }
   for (i=1; i<(1<<(n-1)); ++i) {
      u = ((unsigned int)i << 1);
      for (t=1; t<n; ++t) {
         best[i][t] = VERY_LARGE; last[i][t] = -1;
         if ((u & (1U << t)) == 0) {
            for (j=1; j<n; ++j) if (u & (1U << j)) {
               v = (u ^ (1 << j));
               thiscost = best[v>>1][j] + d[j][t];
               if (thiscost < best[i][t]) {
                  best[i][t] = thiscost; last[i][t] = j;
               }
            }
         }
      }
   }
   bestcost = VERY_LARGE;
   for (t=1; t<n; ++t) {
      u = ((1 << (n-1)) - 1) ^ (1 << (t-1));
      thiscost = best[u][t] + d[t][0];
      if (thiscost < bestcost) {
         bestcost = thiscost;
         bestlast = t;
      }
   }
   p = (int *)malloc(n * sizeof(int));
   p[n-1] = bestlast; j = bestlast; u = ((1 << (n-1)) - 1) ^ (1 << (j-1));
   for (i=n-2; i>=1; --i) {
      j = last[u][j]; p[i] = j; u ^= (1 << (j-1));
   }
   p[0] = 0;
   for (i=0; i<n; ++i) printf("%d%c",p[i],(i==n-1)?'.':'-');
   bestcost = d[p[n-1]][p[0]];
   for (i=0; i<=n-2; ++i) bestcost += d[p[i]][p[i+1]];
   for (i=0; i<(1<<(n-1)); ++i) { free(best[i]); free(last[i]); }
   free(p); free(best); free(last);
   return bestcost;
}

int main ( int argc, char *argv[] )
{
   int n, i;
   int *x, *y, **d;
   int cost;

   srand((unsigned int)time(NULL));
   if (argc == 1) {
      printf("Number of cities = "); scanf("%d", &n);
   } else {
      n = atoi(argv[1]);
   }
   x = (int *)malloc(n * sizeof(int));
   y = (int *)malloc(n * sizeof(int));
   d = (int **)malloc(n * sizeof(int *));
   for (i=0; i<n; ++i) d[i] = (int *)malloc(n * sizeof(int));
   genrand(x,y,d,n);
   free(x); free(y);
   printf("Exact TSP               : "); cost = exactTSP(d,n);  printf(" cost = %d\n", cost);
   printf("Divide-and-Conquer TSP  : "); cost = dncTSP(d,n);    printf(" cost = %d\n", cost);
   printf("Greedy TSP              : "); cost = greedyTSP(d,n); printf(" cost = %d\n", cost);
   printf("Dynamic programming TSP : "); cost = dpTSP(d,n);     printf(" cost = %d\n", cost);
   for (i=0; i<n; ++i) free(d[i]);
   free(d);
   exit(0);
}