#include<cmath>
#include<cfloat>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 105, M = 45;
int n, s[N];
double dp[N][M], ans = DBL_MAX;
struct Point {
	int x, y;
	void read(void) {
		scanf("%d%d", &x, &y);	
	}
	friend double operator - (Point &a, Point &b) {
		return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
	}
}G[N][M];
signed main(void) {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &s[i]);
		for (int j = 1; j <= s[i]; j++)
			G[i][j].read();
	}
	for (int t = 1; t <= s[1]; t++) {
		for (int i = 3; i <= n; i++)
			for (int j = 1; j <= s[i]; j++)
				dp[i][j] = DBL_MAX;
		for (int i = 1; i <= s[2]; i++)
			dp[2][i] = (double)(G[2][i] - G[1][t]);
		for (int i = 3; i <= n; i++)
			for (int j = 1; j <= s[i]; j++)
				for (int k = 1; k <= s[i - 1]; k++)
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + (G[i][j] - G[i - 1][k]));
		for (int i = 1; i <= s[n]; i++)
			ans = min(ans, dp[n][i] + (G[1][t] - G[n][i]));
	}
	cout << (int)(ans * 100) << endl;
}

• Re:40行代码仅供参考 (6) NEIGHTHORN 2016-07-28 12:52:23