该楼层疑似违规已被系统折叠隐藏此楼查看此楼
#include
#include
#define N 6
#define MAX 10000
int bestc=MAX;
int cc=0;
int dis[N+1][N+1]={0,0,0,0,0,0,0,
0,0,10,20,30,40,50,
0,12,0,18,30,25,21,
0,23,19,0,5,10,15,
0,34,32,4,0,8,16,
0,45,27,11,10,0,18,
0,56,22,16,20,12,0};
int x[N+1];
int bestx[N+1];
void swap(int x[N+1],int i,int j)
{
int a;
a=x[i];
x[i]=x[j];
x[j]=a;
}
void backtrack(int i)
{
int j;
if(i==N)
{
if(dis[x[i-1]][x[i]]
dis[x[i]][1]
(bestc==MAX||cc+dis[x[i-1]][x[i]]+dis[x[i]][6]
{
for(j=1;j<=i;j++)
bestx[j]=x[j];
bestc=cc+dis[x[i-1]][x[i]]+dis[x[i]][6];
}
}
else
{
for(j=i;j<=N;j++)
if(dis[x[i-1]][x[j]]
(bestc==MAX||cc+dis[x[i-1]][x[j]]
{
swap(x,i,j);
cc+=dis[x[i-1]][x[i]];
backtrack(i+1);
cc-=dis[x[i-1]][x[i]];
swap(x,i,j);
}
}
}
int main()
{
int i;
for(i=1;i<=N;i++)
{
x[i]=i;
bestx[i]=i;
}
backtrack(2);
printf("bestc=%d\n",bestc);
for(i=1;i<=N;i++)
{
printf("%d ",bestx[i]);
}
getch();
return 0;
}
/*
int i,j;
for(i=0;i
{
for(j=0;j
{
printf("%3d ",dis[i][j]);
}
printf("\n");
}
*/
