记录编号	348759	评测结果	AAAAAAAAAA
题目名称	售货员的难题	最终得分	100
用户昵称	Zwoi_只会打表抄代码的蒟蒻	是否通过	通过
代码语言	C	运行时间	1.029 s
提交时间	2016-11-14 16:02:12	内存使用	0.18 MiB

#include <stdio.h>
#include <stdlib.h>
int n,a[50][50],dis[50],min,x,y;
void swap(int *a,int *b)
{
	int t;
	t=*a;
	*a=*b;
	*b=t;
}
void sv(int a,int b)
{
	int i,j;
	for(i=a,j=b;i<=j;i++,j--)
		swap(&dis[i],&dis[j]);
}
int main()
{
	int i,j,k,t;
	freopen("salesman.in","r",stdin);
	freopen("salesman.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	min=0x7f7f7f7f;
	for(i=1;i<=n;i++)
		dis[i]=i;
	for(i=1;i<=20000;i++)
	{
		t=0;
		for(j=1;j<=100;j++)
		{
			x=rand()%(n)+1;
		    y=rand()%(n)+1;
		    swap(&dis[x],&dis[y]);
		}
		for(k=1;k<n;k++)
			for(j=k+1;j<=n;j++)
				if(a[dis[k-1]][dis[k]]+a[dis[j]][dis[j+1]]>a[dis[k-1]][dis[j]]+a[dis[k]][dis[j+1]])
					sv(k,j);
	    for(j=1;j<n;j++)
			t+=a[dis[j]][dis[j+1]];
		t+=a[dis[n]][dis[1]];
		if(t<min)
			min=t;
    }
	printf("%d",min);
	return 0;
}