记录编号	7058	评测结果	AAAAAAAAAA
题目名称	放养奶牛	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	0.108 s
提交时间	2008-11-06 10:46:05	内存使用	0.45 MiB

#include <iostream>
#include <cmath>

#define MAXN 111
#define INF 1e100

using namespace std;

typedef struct{
	int x,y;
}Point;

int n,ans,many[MAXN];
double f[MAXN][MAXN];
Point pos[MAXN][MAXN];

double dis(int x1,int x2,int y1,int y2)
{
	if (x1==x2 && y1==y2)
		return INF;
	return sqrt( (double) ( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)   )  );
}

void dp()
{
	int i,j,k;
	double zan;
	for (i=1;i<=n;i++)
		for (j=1;j<=many[i];j++)
		{
			f[i][j]=INF;
			for (k=1;k<=many[i-1];k++)
			{
				zan=dis(pos[i][j].x,pos[i-1][k].x,pos[i][j].y,pos[i-1][k].y);
				if (f[i-1][k]+zan<f[i][j])
					f[i][j]=f[i-1][k]+zan;
			}
		}
}

void run()
{
	int i;
	double min;
	many[0]=1;
	min=INF;
	for (i=1;i<=many[n];i++)
	{
		pos[0][1].x=pos[n][i].x;
		pos[0][1].y=pos[n][i].y;
		dp();
		if (f[n][i]<min)
			min=f[n][i];
	}
	ans=(int)(min*100+0.00000001);
}

void ini()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>many[i];
		for (int j=1;j<=many[i];j++)
			cin>>pos[i][j].x>>pos[i][j].y;
			
	}
}

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