#include <cstdio>
#include <cmath>

const int maxn=110,maxm=60,oo=2134000000;

int n,s[maxn];
int x[maxn][maxm],y[maxn][maxm];
long double dp[maxn][maxm];

long double Distance(int x1,int y1,int x2,int y2)
{
	return sqrt( (x1-x2) * (x1-x2)+(y1-y2) * (y1-y2) );
}
int main()
{
	freopen("p2173.in","r",stdin);
	freopen("p2173.out","w",stdout);
	
	scanf("%d",&n);
	for (int i=2;i<=n;i++)
	for (int j=1;j<=maxm;j++)
	dp[i][j]=oo;
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&s[i]);
		for (int j=1;j<=s[i];j++)
		scanf("%d%d",&x[i][j],&y[i][j]);
	}
	for (int i=2;i<=n;i++)
	{
		for (int j=1;j<=s[i];j++)
		for (int k=1;k<=s[i-1];k++)
		if (dp[i-1][k]+Distance(x[i-1][k],y[i-1][k],x[i][j],y[i][j])<dp[i][j])
		dp[i][j]=dp[i-1][k]+Distance(x[i-1][k],y[i-1][k],x[i][j],y[i][j]);
	}
	long double min=oo;
	for (int i=1;i<=s[1];i++)
	for (int j=1;j<=s[n];j++)
	if (dp[n][j]+Distance(x[1][i],y[1][i],x[n][j],y[n][j])<min)
	min=dp[n][j]+Distance(x[1][i],y[1][i],x[n][j],y[n][j]);
	min=min * 100;
	int ans=int(min);
	printf("%d\n",ans);
	return 0;
}

• Re:这样为什么WA啊，我实在是看不出来了！ (1197) suhang 2010-01-13 20:23:10