HDOJ 1875 원활 한 공사 재 개

//HDU 1875 AC
#include <iostream>
#include <cmath>

using namespace std;
#define MAX 100010
#define LEN 105
double dist[LEN];
double map[LEN][LEN];
bool isvisited[LEN];

//     
typedef struct Point{
	double x;
	double y;
}Point;

//   
void init(){
	int i,j;
	for(i=0;i<LEN;i++){
		for(j=0;j<LEN;j++){
			if(i==j) map[i][j]=0;   // a[][]     ，    ；
			map[i][j]=MAX;
		}
	}
}

//      
double caculteD(Point a,Point b){
	double len;
	len=sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
	return len;

}

//prim  
double prim(int n){
	int i,j,min,pos;
	double sum=0;
	memset(isvisited,false,sizeof(isvisited));

	//   
	for(i=1;i<=n;i++){
		dist[i]=map[1][i];
	}

	// 1  
	isvisited[1]=true;
	dist[1]=MAX;

	//             
	for(i=1;i<n;i++){
		min=MAX;
		//pos=-1;
		for(j=1;j<=n;j++){
			if(!isvisited[j] && dist[j]<min){
				min=dist[j];
				pos=j;
			}
		}	
		if(min==MAX){
			return -1;

		}
		sum+=dist[pos];//    
		isvisited[pos]=true;

		//    
		for(j=1;j<=n;j++){
			if(!isvisited[j] && dist[j]>map[pos][j]){
				dist[j]=map[pos][j];
			}
		}
	}	
	return sum;
}

int main(){
	Point p[105];
    int i,j,n,nCase;
	cin>>nCase;
	double result;//  
	while(nCase--){
		cin>>n;
		init();	//   
		for(i=1;i<=n;i++){
			scanf("%lf%lf",&p[i].x,&p[i].y);
		}
		for(i=1;i<n;i++){
            for(j=i+1;j<=n;j++){  
				double len;
                len=caculteD(p[i],p[j]);
				if(len>=10 && len<=1000){//     
					map[i][j]=map[j][i]=100*len;// *100  
				}  
            }
		}
		result=prim(n);
		if(result==-1){
			cout<<"oh!"<<endl;
		}
		else{
			printf("%.1lf
",result);
		}
	}
	 return 0;
}