第一次写的没有加入路径.c

来自「旅行商问题 某售货员要到若干城市去推销商品」· C语言 代码 · 共 66 行

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define MAX 100000
#define INFINITY 100000

int d[21][MAX]={INFINITY};

int main(){
	int i,j,k,t,n;
	long min;
	int c[21][21]={0};
	char str[100];

	printf("Input the filename:\n");
	scanf("%s",str);
	if(freopen(str,"r",stdin)==NULL){
		printf("open file error\n");
		exit(1);
	};
 	scanf("%d",&n);

	for(i=0;i<n;i++)
		for(j=0;j<n;j++){
			scanf("%d",&c[i][j]);
			if(c[i][j]==0) c[i][j]=INFINITY;
		}
	
	for(i=1;i<n;i++){
		d[i][0]=c[i][0];
//		printf("%d ",d[i][0]);
		}

	t=1;
	for(i=1;i<=n-1;i++)
		t=t*2;
	t=t-1;
	
	for(i=1;i<=t;i++){

		for(j=1;j<n;j++){
			min=INFINITY;
			if(((i>>j-1)&1)==0){

				for(k=1;k<n;k++)
				if(((i>>(k-1))&1)!=0)
					if(c[j][k]+d[k][i-(1<<(k-1))]<min)
						min=d[k][i-(1<<(k-1))]+c[j][k];
				d[j][i]=min;
			//	printf("%d ",min);
			}//if((i&(1<<j)
//			printf("%d ",min);
			}//for j

		printf("\n");
	}//for i
//	printf("t is %d\n",t);
	
	min=INFINITY;
	for(i=1;i<n;i++)
		if(min>c[0][i]+d[i][t^(1<<(i-1))])
			min=c[0][i]+d[i][t^(1<<(i-1))];
		printf("%d\n",min);
	return 1;
}