岛国问题

【问题描述】一家互联网服务商（简称PIN）在太平洋上发现了几座新岛屿，其中最大的一个岛（称为主岛）已经连接到Internet，但是其他岛和主岛之间没有光缆连接，所以无法上网。为了让所有岛上的居民都能上网，每个岛和主岛之间都必须有直接或者间接的光缆连接。
下图就是这样的一个岛屿，每条实线表示一根光缆，它的长度等于两个岛屿中心位置（路由器位置）的几何距离，图上的数字是该岛上的居民数量。为了节省成本，所有光缆的总长度尽量小。

岛屿之间的光缆同时开始铺设，以每天一公里的速度铺设，那么较短的路径肯定先铺设完，某岛屿只要与主岛之间存在一条已经铺设好的电缆，就能接入互联网。PIN非常关注所有居民的平均接入互联网的时间，假设第 i 个岛屿的居民人数是mi ，接入互联网需要的时间是ti ，则平均接入时间是：

【输入形式】输入内容包括所有岛屿的信息。第一行是岛屿的个数n（n< 50）；接下来共有n行，每一行包括三个正整数：xi yi mi ，中间空格隔开，（xi , yi )是岛屿的位置坐标，坐标轴单位是公里，mi 是该岛屿的居民人数。输入的第一个岛屿是主岛。
【输出形式】输出所有居民的平均接入互联网的平均天数，结果保留两位小数。
【样例输入】

7
11 12 2500
14 17 1500
9 9 750
7 15 600
19 16 500
8 18 400
15 21 250
【样例输出】3.20
【样例说明】不用考虑岛屿之间具有相同距离的情况

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n;
double mp[55][55];

struct node{
	int x, y, num;
}a[55];

double dist[55], tim[55];
int vis[55];
int people_num;

void prim(){
	for (int i = 1; i <= n; i++){
		dist[i] = mp[i][1];
		vis[i] = 1;
	}
	vis[1] = -1;
	tim[1] = 0;
	for (int i = 2; i <= n; i++){
		double minn = 1.0 * 0x3f3f3f3f;
		int v = -1;
		for (int j = 1; j <= n; j++){
			if(vis[j] != -1 && minn > dist[j]){
				minn = dist[j];
				v = j;
			}
		}
		if(v != -1){
			if(dist[v] <= tim[vis[v]]){
				tim[v] = tim[vis[v]];
			}else{
				tim[v] = dist[v];
			}
		}
		vis[v] = -1;
		for (int j = 1; j <= n; j++){
			if(vis[j] != -1 && dist[j] > mp[v][j]){
				dist[j] = mp[v][j];
				vis[j] = v;
			}
		}
	}
}

void solve(){
	double sum = 0;
	for (int i = 1; i <= n; i++){
		sum += tim[i] * a[i].num;
	}
	printf("%.2lf\n", sum / people_num);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].num);
		people_num += a[i].num;
	}
	for (int i = 1; i <= n; i++){
		for (int j = i + 1; j <= n; j++){
			mp[i][j] = mp[j][i] = sqrt((double)((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y)));
		}
	}
	prim();
	solve();

	return 0;
}
/**/