记录编号	386277	评测结果	AAAAAAAAAA
题目名称	线型网络	最终得分	100
用户昵称	泪寒之雪	是否通过	通过
代码语言	C++	运行时间	0.100 s
提交时间	2017-03-24 08:02:15	内存使用	7.92 MiB

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
 
int n;
FILE *fi=fopen("linec.in","r"),*fo=fopen("linec.out","w");
double dis[1000][1000];
int lt[1000];
 
double dist(double a1,double b1,double a2,double b2)
{
	return sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2));
}
 
void init()
{
	int i,j;
	double a[1000],b[1000];
 
	fscanf(fi,"%d",&n);
 
	for (i=1;i<=n;i++)
	{
		fscanf(fi,"%lf%lf",&a[i],&b[i]);
	}
 
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			dis[i][j]=dist(a[i],b[i],a[j],b[j]);
	
	for (i=0;i<=n;i++)
    {
        dis[0][i]=0;
        dis[i][n+1]=0;
    }
	
	for (i=1;i<=n;i++)
	{
		lt[i]=i;
	}
 
}
 
void swap(int& a,int& b)
{
	int t;
	t=a;
	a=b;
	b=t;
}
 
void mkhmd()
{
	int i,a,b;
 
	for (i=1;i<=100;i++)
	{
		a=rand()%(n-1)+1;
		b=rand()%(n-1)+1;
		swap(lt[a],lt[b]);
	}
}
 
void sv(int a,int b)
{
	int i,j;
	for (i=a,j=b;i<=j;i++,j--)
	{
		swap(lt[i],lt[j]);
	}
}
 
void change()
{
	int i,j;
	for (i=1;i<=n-1;i++)
	{
		for (j=i+1;j<=n;j++)
		{
			if (dis[ lt[i-1] ][ lt[i] ]+dis[ lt[j] ][ lt[j+1] ] > dis[ lt[i-1] ][ lt[j] ]+dis[ lt[i] ][ lt[j+1] ])
			{
				sv(i,j);
			}	
		}
	}
}
 
double count()
{
	int i;
	double r=0;
	for (i=1;i<=n-1;i++)
	{
		r+=dis[ lt[i] ][ lt[i+1] ];
	}
	return r;
}
 
int main()
{
	double c,mc=10000000;
	init();
 
	for (int i=1;i<=2000;i++)
	{
		mkhmd();
		change();
		c=count();
		if (c<mc)
			mc=c;
	}
 
	fprintf(fo,"%.2lf",mc);
	fclose(fi);
	fclose(fo);
	return 0;
}