/* ******************************************************
   programma per il problema del commesso viaggiatore
   Dato un insieme di n citta' e un valore "limite" si vuole 
   trovare se esiste un percorso chiuso di costo <limite che 
   le visita tutte esattamente una volta 
   ****************************************************** */
#include <math.h>
#include <stdio.h>


// funzione che fornisce la distanza fra citta'
// notare che la distanza puo' essere asimmetrica
double dist(int i, int j)
{
  if(i==j+3) return 1;
  return 1 + fabs(7+i-j); 
}

// procedura ricorsiva per la soluzione del tsp
// cur: citta in cui mi trovo attualmente
// numvis: numero di citta' visitate
// vis[]: array che indica quali citta' sono state visitate
// n: numero totale di citta'
// perc: distanza percorsa fino a questo punto
// limite: distanza massima che si vuole percorrere
int tsp(int cur, int numvis, char vis[], int n, double perc, double limite)
{
  int i;

  if(perc > limite)
    return 0;
  
  if(numvis==n) {
    if(perc+dist(cur,0) <= limite) {
      printf("Costo %f\n", perc+dist(cur,0));
      printf("Percorso (inverso): %d %d(%.2f)",0,cur,dist(cur,0));
      return 1;
    } else
      return 0;
  }

  // ci sono ancora citta da visitare
  for(i=0;i<n;i++) {
    if(vis[i]) continue;  // i gia' visitata
    vis[i]=1;
    if(tsp(i,numvis+1,vis,n,perc+dist(cur,i),limite)) {
      printf(" %d(%.2f)",cur,dist(cur,i));
      return 1;
    }
    vis[i]=0;
  }
  return 0;
}


#define NMAX 200
char visitate[NMAX] = {0};

int main()
{
  int n;
  double limite;

  printf("Inserisci il numero di citta' e il limite \n");
  scanf("%d %lf",&n,&limite);
  if(n>=NMAX) printf("numero max: %d\n",NMAX);
  else if(n<2) printf("Ci vogliono almeno 2 citta'\n");
  else {
    // si parte dalla citta' 0
    visitate[0]=1;
    if(tsp(0,1,visitate,n,0,limite))
      printf("\n");
    else
	  printf("Nessuna soluzione\n");
  }
  return 0;
}