Blue Bridge Cup provincial match simulation question 9 (MST)

Blue Bridge Cup provincial match simulation Question 9

Problem description
　 2015 year , All over China, household electricity has been realized . As a Power Builder , Xiao Ming is helping one belt, one road, the other country .
　 This time, , Xiao Ming wants to help n The village is electrified , among 1 A power station can be built in Village No , The electricity is enough for all the villages .
　 Now? , this n There are no wires between the villages , Xiao Ming's main task is to set up wires to connect these villages , So that all villages are directly or indirectly connected to power stations .
　 Xiao Ming measured the location of all the villages （ coordinate ） And height , If you want to connect two villages , Xiao Ming needs to spend the coordinate distance between the two villages plus the square of the height difference , Formally described as coordinates by (x_1, y_1) The height is h_1 The village and coordinates are (x_2, y_2) The height is h_2 The cost of the connection between villages is
　 sqrt((x_1-x_2)(x_1-x_2)+(y_1-y_2)(y_1-y_2))+(h_1-h_2)*(h_1-h_2).
　 In the upper form sqrt Denotes the square root in brackets . Notice the position of the brackets , The calculation method of height is different from that of abscissa and ordinate .
　 Because of the limited funds , Please help Xiao Ming calculate how much it will cost him to make this n All villages are electrified .

Input format
　 The first line of input contains an integer n , It means the number of villages .
　 Next n That's ok , Every three integers x, y, h, It means the horizontal of a village 、 Ordinates and heights , The first village could build a power station .

Output format
　 Output one line , Contains a real number , Rounding reservation 2 Decimal place , Answer .

The sample input
4
1 1 3
9 9 7
8 8 6
4 5 4

Sample output
17.41

Evaluate use case size and conventions
　 about 30% The evaluation case of ,1 <= n <= 10;
　 about 60% The evaluation case of ,1 <= n <= 100;
　 For all profiling use cases ,1 <= n <= 1000,0 <= x, y, h <= 10000.

tips: Bare minimum spanning tree . Note the data range , Go straight up Prim（ Because the data is just 1000, And calculate the distance of each point , Use adjacency matrix directly +prim that will do , No heap optimization （ If the edge is still used kruskal Write mst））.

#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;

int n,cnt,vis[1005];
struct node{
    
	double x,y,h;
}book[1005];
double mp[1005][1005],dis[1005],sum; 
double getdis(int i, int j){
    
	return sqrt((book[i].x - book[j].x) * (book[i].x - book[j].x) + (book[i].y - book[j].y) * (book[i].y - book[j].y)) + 
	(book[i].h - book[j].h) * (book[i].h - book[j].h);
}

int main(){
    
	scanf("%d",&n);
	for(int i = 1; i <= n; ++i){
    
		for(int j = 1; j <= n; ++j)
			if(i == j)	mp[i][j] = 0;
			else mp[i][j] = inf;
	}
	for(int i = 1; i <= n; ++i)
		scanf("%lf%lf%lf",&book[i].x,&book[i].y,&book[i].h);
	for(int i = 1; i <= n; ++i){
    
		for(int j = i + 1; j <= n; ++j)
			mp[i][j] = mp[j][i] = getdis(i,j);
	}
	for(int i = 1; i <= n; ++i)
		dis[i] = mp[1][i];	
	vis[1] = 1, cnt++;
	//Prim
	while(cnt < n){
    
		int minn = inf,u;
		for(int j = 1; j <= n; ++j){
    
			if(!vis[j] && dis[j] < minn){
    
				u = j,minn = dis[j];
			}
		}
		vis[u] = 1,cnt++;
		sum += dis[u];
		for(int v = 1; v <= n; ++v){
    
			if(!vis[v] && dis[v] > mp[u][v])
				dis[v] = mp[u][v];
		}
	}
	printf("%.2lf",sum);
	return 0;
}