Travelling Salesman

#include<iostream>
#include<fstream.h>
#define max 100         //So thanh pho toi da
#define maxE  10000     //Chi phi toi da cua moi chang duong
#define maxC  max*maxE // {+oo}
#define Chua_Di 0
#define Da_Di 1

int dmin =  maxE; // Chi phi nho nhat trong tat ca cac changg duong
int C[max+1][max+1],X[max +2],BestWay[max+2],T[max+2];
bool Free[max]; //Free de danh dau
                //Free[i] = True neu Tp i chua di qua
int n,m; // n thanh pho va m tuyen duong truc tiep
long MinSpending; //Chi phi hanh trinh toi uu;


void Enter()
{
     int i,j;
     ifstream f;
     f.open( "Nguoi_du_lich.txt");
     f>>n>>m;
     if(!f.is_open())std::cout<<"Can't able to file. " <<std::endl;
     //Khoi tao mang chi phi
     for( i=1; i<=n;++i)
     for( j=1; j<=n;++j)
     {
             if( i ==j)C[i][j] =0;
             else C[i][j] = maxC;
     }
     
     //Nhap chi phi cua m tuyen duong
     
     for( int k=1;k<=m;++k)
     {
          f>>i>>j>>C[i][j];
          C[j][i] = C[i][j];//Chi phi nhu nhau tren 2 chieu
          //std::cout<<" "<<C[i][j];
          if( C[i][j] <dmin)dmin = C[i][j];
     }
     
}

void Init()
{
     Free[1] = Da_Di;
     X[1] = 1; //Xuat phat tu thanh pho 1
     T[1] = 0; //Chi phi xuat phat bang 0
     MinSpending = maxC;
}

void Attempt(int i )
{
     for( int j=2;j<=n;++j) //Thu cac Tp tu 2 den n
     {
          if (Free[j]== Chua_Di) // Neu chua gap Tp di qua
          {
                        X[i] =j; //Thu di
                        T[i] = T[i-1] + C[X[i-1]][j];
                        //Chi phi = Chi phi buoc truoc + Chi phi duong di truc tiep;
                        if( T[i] <MinSpending)
                        {
                            //Hien nhien neu co dk nay thi C[X[i-1],j] < +oo
                            
                            if( i==n)
                            {
                                if( (T[n] + C[X[n]][1]) < MinSpending )
                                {
                                //Tu X[n] quay lai 1 van ton chi phi it hon truoc
                                //Cap nhat BestConfig
                                //BestWay = X;
                                for( int k =1;k<=n;++k)
                                BestWay[k] = X[k];
                                
                                //Chi phi thap hon
                                MinSpending = T[n] + C[X[n]][1];
                                }
                            }
                            else if( T[i] + (n-i+1)* dmin < MinSpending)
                            {
                                Free[j] = Da_Di;//Danh dau thanh pho vua di qua
                                Attempt(i+1); // Tim cac kha nang  chon x[i+1]
                                Free[j] = Chua_Di; // Bo danh dau
                            }
                        }
          }
     }
     
     
}

void PrintResult()
{
     if(MinSpending == maxC) 
     {
        std::cout<< "NO SOLUTION. ";
     }
     else
     {
         for( int i=1;i<=n;++i)
         {
              std::cout<<BestWay[i]<< "->";
         
         }
         std::cout<<1 << " Cost : " << MinSpending;
     }
     
}

int main()
{
    Enter();
    Init();
    Attempt(2);
    PrintResult();
    system("pause");
    return 0;
}