#include<conio.h>

#include<math.h>

#include<stdio.h>

int c[20][20],a[20],xopt[20],chuaxet[20],n,fopt,cmin,can;

void nhapdulieu();

void init();

void Try(2);

void ketqua();

void main()

{

clrscr();

nhapdulieu();

init();

Try(2);

ketqua();

getch();

}

void nhapdulieu()

{

int i,j;

printf("Nhap so thanh pho: ");scanf("%d",&n);

printf("nhap ma tran chi phi c[i][j]

");

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

{

printf("c[%d][%d]= ",i,j);scanf("%d",&(c[i][j]));

}

printf("

MA TRAN CHI PHI BAN DAU LA:

");

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++) printf("%4d",c[i][j]);

printf("

");

}

cmin=0;

for (i=1;i<=n;i++)

for(j=1;j<=n;j++)

if ((cmin>c[i][j])&&(i!=j)) cmin=c[i][j];

}

void ghinhan()

{

int i,sum;

sum=(can+c[a[n]][a[1]]);

if (sum<fopt)

{

for (i=1;i<=n;i++) xopt[i]=a[i];

fopt=sum;

}

}

void Try(int i)

{

int j;

//co dinh thanh pho xuat phat la thanh pho 1//

// duyet (n-1)! hanh trinh theo nhanh can//

for (j=2;j<=n;j++)

if (chuaxet[j])

{

a[i]=j;

chuaxet[j]=0;

can+=c[a[i-1]][a[i]];

if (i==n) ghinhan();

else

if (can+(n-i+1)*cmin<fopt) Try(i+1);

can-=c[a[i-1]][a[i]];

chuaxet[j]=1;

}

}

void ketqua()

{

int i,j;

printf("

hanh trinh toi uu co chi phi la :%5d

",fopt);

for (i=1;i<=n;i++)

printf("%2d--->" ,xopt[i]);

printf("%2d",xopt[1]);

}

void init()

{

int i,j;

cmin=0;

for (i=1;i<=n;i++)

{

chuaxet[i]=1;

for (j=1;j<=n;j++)

if ((i!=j)&&(cmin>c[i][j])) cmin=c[i][j];

}

fopt=32767;//gia su fopt ban dau lay gia tri lon nhat maxint trong pascan//

can=0;

a[1]=1;

}