#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#define LENGTH 25
struct Path{
char pass[LENGTH+1];
int min_distance;
int nextcity;
struct Path *next;
};
int C[LENGTH][LENGTH];
struct Path *G[LENGTH][LENGTH];
char S[LENGTH+1];
int S_init(int n)
{
int i;
for(i=0;i<n;i++)
S[i] = '0';
S[i] = '\0';
}
int Getmin(int j,int num_c,char *S)
{
struct Path *pre_min;
pre_min = G[j][num_c-1];
while(pre_min!=NULL){
if(strcmp(pre_min->pass,S)==0){
return(pre_min->min_distance);
printf("OK!!!!\n");
break;
}
pre_min = pre_min->next;
}
return 30000;
}
int insert_temp1(int n,int i,int num_c,int j,char *S,struct Path *G[LENGTH][LENGTH])
{
int k;
int new_distance;
G[i][num_c] = (struct Path *)malloc(sizeof(struct Path));
G[i][num_c]->next = NULL;
S[j] = '1';
strcpy(G[i][num_c]->pass,S);
G[i][num_c]->min_distance = 30000;
for(k=1;k<n;k++){
if(k == i)
continue;
if(S[k] == '1'){
S[k] = '0';
new_distance = C[i][k]+Getmin(k,num_c,S);
S[k] = '1';
if(G[i][num_c]->min_distance > new_distance){
G[i][num_c]->min_distance = new_distance;
G[i][num_c]->nextcity = k;
}
}
}
S[j] = '0';
}
int insert_temp(int n,int i,int num_c,int j,char *S,struct Path *G[LENGTH][LENGTH])
{
int k;
struct Path *temp;
int new_distance;
temp = (struct Path *)malloc(sizeof(struct Path));
temp->next = NULL;
S[j] = '1';
strcpy(temp->pass,S);
temp->min_distance = 30000;
for(k=1;k<n;k++){
if(k == i)
continue;
if(S[k] == '1'){
S[k] = '0';
new_distance = C[i][k]+Getmin(k,num_c,S);
S[k] = '1';
if(temp->min_distance > new_distance){
temp->min_distance = new_distance;
temp->nextcity = k;
}
}
}
temp->next = G[i][num_c]->next;
G[i][num_c]->next = temp;
S[j] = '0';
}
int Trip(int n,char *S,struct Path *G[LENGTH][LENGTH])
{
int i,j;
int num_c;
struct Path *creat_temp,*new_temp;
for(num_c = 1;num_c<n-1;num_c++){//列号
S_init(n);
for(i=1;i<n;i++){//行号
creat_temp = G[i][num_c-1];
while(creat_temp!=NULL){
S_init(n);
strcpy(S,creat_temp->pass);
for(j=1;j<n;j++){
if(j == i||S[j] == '1')
continue;
S[j]='1';
if(G[i][num_c] == NULL)
insert_temp1(n,i,num_c,j,S,G);
else{
new_temp = G[i][num_c];
while(new_temp){
if(strcmp(new_temp->pass,S) == 0)
break;
new_temp=new_temp->next;
}
if(new_temp == NULL)
insert_temp(n,i,num_c,j,S,G);
}
S[j]='0';
}
creat_temp = creat_temp->next;
}
}
}
}
int main(int argc,char **argv)
{
int n,i,j;
int min = 30000;
int num_way;
struct Path *temp;
struct Path *aa;
printf("please input the data first :\n");
printf("the nauber of city is : ");
scanf("%d",&n);
printf("\nthe data is :\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&C[i][j]);
printf("the data is :\n");
for(i=0;i<n;i++){
for(j=0;j<n;j++)
printf("%d ",C[i][j]);
printf("\n");
}
S_init(n);
for(i=1;i<n;i++){
G[i][0] = (struct Path *)malloc(sizeof(struct Path));
strcpy(G[i][0]->pass,S);
G[i][0]->min_distance = C[i][0];
G[i][0]->nextcity = -1;
G[i][0]->next = NULL;
}
for(i=0;i<n;i++)
for(j=1;j<n;j++)
G[i][j] = NULL;
Trip(n,S,G);
for(j=0;j<n-1;j++){
for(i=1;i<n;i++){
aa = G[i][j];
while(aa){
printf("hhhhhh %d %d %s %d next %d\n",i,j,aa->pass,aa->min_distance,aa->nextcity);
aa = aa->next;
}
}
}
for(i=1;i<n;i++){
if(min > (C[0][i]+G[i][n-2]->min_distance)){
min = C[0][i]+G[i][n-2]->min_distance;
num_way = i;
}
}
printf("the result is : %d\n", min);
printf("0 ");
S[0] = '0';
for(i=1;i<n;i++)
S[i] = '1';
S[n] = '\0';
for(i=n-2;i>=0;i--){
S[num_way] = '0';
temp = G[num_way][i];
while(temp){
if(!strcmp(S,temp->pass)){
printf("%d ",num_way);
num_way = temp->nextcity;
break;
}else{
temp = temp->next;
}
}
}
printf(" 0 \n");
}
