#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

struct cow{
	int pnum;   //喜欢地点的个数
	int loc[50][2]; //这里是牛所喜欢的地点
} cows[102];
int cowxy[102][2];     //记录个牛所喜欢的坐标


int cownum;

double caldis(double x,double y,double xx,double yy){
	return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
double calcowdis(int x,int y){  //第x和第y只牛
	return caldis(cowxy[x][0],cowxy[x][1],cowxy[y][0],cowxy[y][1]);
}


double cal(int k){
	if(k==cownum)return 0;
	if(k==cownum-1){
		int pnum=cows[k].pnum;
		double sum=10000.0;
		for(int i=0;i<pnum;i++){
			cowxy[k][0]=cows[k].loc[i][0];
			cowxy[k][1]=cows[k].loc[i][1];
			double dis1=calcowdis(k,0);
			double dis2=calcowdis(k,k-1);
			if(dis1+dis2<sum){
				sum=dis1+dis2;
			}
		}
		return sum;
	}else if(k==0){
		int prefern=cows[0].pnum;
		double min=10000.0;
		for(int i=0;i<prefern;i++){
			cowxy[0][0]=cows[0].loc[i][0];
			cowxy[0][1]=cows[0].loc[i][1];
			double tmp=cal(1);
			if(tmp<min){
				min=tmp;
			}
		}		
		return min;
	}else{
		int prefern=cows[k].pnum;
		double min=10000.0;
		for(int i=0;i<prefern;i++){
			cowxy[k][0]=cows[k].loc[i][0];
			cowxy[k][1]=cows[k].loc[i][1];
			double lastdis=calcowdis(k,k-1);
		//	return lastdis;
			double other=cal(k+1);
			if(lastdis+other<min){
				min=lastdis+other;
			}
		}
		return min;
	}
}


void main(){
//	ifstream cin("data.txt");
	cin>>cownum;
	for(int i=0;i<cownum;i++){
		cin>>cows[i].pnum;
		//cout<<cows[i].pnum<<" ";
		for(int j=0;j<cows[i].pnum;j++){
			int x,y;
			cin>>x>>y;
			cows[i].loc[j][0]=x+100;cows[i].loc[j][1]=y+100;
		//	cout<<cows[i].loc[j][0]<<" "<<cows[i].loc[j][1]<<" ";
		}
	//	cout<<endl;
		for(j=0;j<cownum;j++){
			cowxy[j][0]=cowxy[j][1]=-1;
		}
	}
	double tmp=cal(0);
	cout<<int(tmp*100)<<endl;
}

• 我也DFS超时，优化成递推后AC (66) sgzxy 2008-06-17 19:37:12