记录编号	345904	评测结果	AAAAAAAAAA
题目名称	放养奶牛	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2016-11-11 19:32:19	内存使用	1.67 MiB

#include <cstdio>
#include <cmath>
const int MAXS=40;
const int MAXN=110;
const int MAXC=MAXN*MAXS;
const double INF=1E10;
int x[MAXC],y[MAXC];
int s[MAXN];
double f[MAXS][MAXN][MAXS];

inline bool
equal(int i,int j){
	return x[i]==x[j]&&y[i]==y[j];
}
inline int 
$(int a,int b){
	return a*41+b;
}
inline double
min(double a,double b){
	return a<b?a:b;
}
inline double 
dis(int i,int j){
	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main(){
	freopen("cowties.in","r",stdin);
	freopen("cowties.out","w",stdout);
	int N;scanf("%d",&N);
	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)]);
		}
	}s[++N]=s[1];
	for(int i=1;i<=s[1];++i){
		x[$(N,i)]=x[$(1,i)];
		y[$(N,i)]=y[$(1,i)];
	}
	for(int c=1;c<=s[1];++c)
		for(int i=1;i<=N;++i)
			for(int j=1;j<=s[i];++j)
				f[c][i][j]=INF;
	for(int c=1;c<=s[1];++c){
		f[c][1][c]=0.0;
	}
	for(int c=1;c<=s[1];++c){
		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(equal($(i,j),$(i-1,k)))continue;
					f[c][i][j]=min(f[c][i][j],f[c][i-1][k]+dis($(i,j),$(i-1,k)));
				}
				//printf("[%d][%d][%d]:=%.2lf\n",c,i,j,f[c][i][j]);
			}
		}
	}double ans=INF;
	for(int c=1;c<=s[1];++c){
		ans=min(ans,f[c][N][c]);
	}printf("%d",(int)(ans*100));
	return 0;
}