比赛 noip20081103 评测结果 WWTTTTTTTA
题目名称 放养奶牛 最终得分 10
用户昵称 zqzas 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2008-11-03 22:07:01
显示代码纯文本
#include <iostream>
#include <cmath>

#define MAXN 111
#define INF 99999999

using namespace std;

int n,many[MAXN],pos[MAXN][3],hash[MAXN*2][MAXN*2],data[MAXN][MAXN][3];
double ans;

inline double far(int x1,int y1,int x2,int y2)
{
	return sqrt( ((double)(x1-x2))*((double)(x1-x2))+ ((double)(y1-y2))*((double)(y1-y2)) );
}

void dfs(int x,double now)
{
	if (x>=n)
	{
		double zan;
		zan=now-far(pos[n-1][0],pos[n-1][1],0,0)+far(pos[n-1][0],pos[n-1][1],pos[0][0],pos[0][1]);
		if (zan<ans)
			ans=zan;
		return;
	}
	if (now>ans)
	   return;
	int a,b;
	for (int i=0;i<many[x+1];i++)
	{
		a=data[x+1][i][0];
		b=data[x+1][i][1];
		if (hash[a][b]==0)
		{
			hash[a][b]=1;
			pos[x+1][0]=a;
			pos[x+1][1]=b;
			dfs(x+1,now+far(pos[x][0],pos[x][1],a,b));
			hash[a][b]=0;
			pos[x+1][0]=0;
			pos[x+1][1]=0;
		}
	}		
}

void run()
{
	many[n]=1;
	ans=INF;
	for (int i=0;i<many[0];i++)
	{
		pos[0][0]=data[0][i][0];
		pos[0][1]=data[0][i][1];
		dfs(0,0);
	}
}

void ini()
{
	cin>>n;
	for (int i=0;i<n;i++)
	{
		cin>>many[i];
		for (int j=0;j<many[i];j++)
		{
			cin>>data[i][j][0]>>data[i][j][1];
			data[i][j][0]+=100;
			data[i][j][1]+=100;
		}
	}
}

int main()
{
	freopen("cowties.in","r",stdin);
	freopen("cowties.out","w",stdout);
	ini();
	run();
	cout<<(int)(ans*100);
	return 0;
}