记录编号	345403	评测结果	AAAAAAAAAA
题目名称	放养奶牛	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	0.059 s
提交时间	2016-11-11 07:18:46	内存使用	0.32 MiB

#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;
int N;
vector<pair<int, int> > p[maxn];
double f[maxn][51];

double dis(pair<int,int> a, pair<int,int> b) {
	int x = a.first-b.first;
	int y = a.second-b.second;
	if(!x&&!y) return 1e10;
	// printf("%.2lf\n", sqrt(x*x+y*y));
	return sqrt(x*x+y*y);
}
int main() {
	freopen("cowties.in","r",stdin);
	freopen("cowties.out","w",stdout);
	scanf("%d", &N);
	for(int i=1,sz; i<=N; ++i) {
		scanf("%d", &sz);
		for(int j=1,x,y; j<=sz; ++j) {
			scanf("%d %d", &x, &y);
			p[i].push_back(make_pair(x, y));
		}
	}
	p[0] = p[N];
	double ans = 1e10;
	for(int l=0; l<(int)p[0].size(); ++l) {
		memset(f, 0, sizeof f);
		for(int i=0; i<(int)p[0].size(); ++i)
			if(l!=i) f[0][i] = 1e10; 
		for(int i=1; i<=N; ++i) {
			for(int j=0; j<(int)p[i].size(); ++j) {
				f[i][j] = 1e10;
				for(int k=0; k<(int)p[i-1].size(); ++k) {
					// printf("%d %d (%d,%d)-(%d,%d)\n", i, j, p[i][j].first, p[i][j].second, p[i-1][k].first, p[i-1][k].second);
					f[i][j] = min(f[i][j], f[i-1][k]+dis(p[i][j], p[i-1][k]));
				}
			}
		}
		ans = min(ans, f[N][l]);
	}
	printf("%d\n", int(ans*100));
	getchar(), getchar();
	return 0;
}