本文共 2132 字，大约阅读时间需要 7 分钟。

Problem Description

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。

Input

输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。
每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。

Output

每组输入数据输出一行，代表建桥的最小花费，结果保留一位小数。如果无法实现工程以达到全部畅通，输出”oh!”.

Sample Input

2
2
10 10
20 20
3
1 1
2 2
1000 1000

Sample Output

1414.2
oh!

题解

• 直接建图跑就好了，用堆优化一下
• 注意数组范围，双向边

AC-Code

#include <iostream>#include <algorithm>#include <queue>#include <functional>#include <string.h>using namespace std;const int maxn = 1e2 + 3;typedef pair<double, int> pdi;struct EDGE {   	int to, next;	double val;}edge[maxn * maxn]; // 别开小了！int head[maxn];int cnt;void add(int u, int v, double w) {   	edge[cnt].to = v;	edge[cnt].val = w;	edge[cnt].next = head[u];	head[u] = cnt++;}int n;double ans;bool vis[maxn];double dis[maxn];void init() {   	cnt = 0;	memset(head, -1, sizeof head);		ans = 0;	fill(dis, dis + maxn, 1 << 30);	memset(vis, false, sizeof vis);}bool prime(int start) {   	priority_queue<pdi,vector<pdi>,greater<pdi> > q;	q.push(make_pair(0, start));	int count = 0;	while (!q.empty() && count < n) {   		int u = q.top().second;		double w = q.top().first;		q.pop();		if (vis[u])    continue;		vis[u] = true;		++count;		ans += w;		for (int i = head[u]; ~i; i = edge[i].next) {   			int v = edge[i].to;			if (!vis[v] && dis[v] > edge[i].val) {   				dis[v] = edge[i].val;				q.push(make_pair(dis[v], v));			}		}	}	return count == n;}int Px[maxn];int Py[maxn];int main() {   	int T;	double distance;	scanf("%d", &T);	while (T--) {   		init();		scanf("%d", &n);		for (int i = 0; i < n; ++i) {   			scanf("%d", &Px[i]);			scanf("%d", &Py[i]);			for (int j = 0; j < i; ++j) {   				distance = sqrt((Px[i] - Px[j]) * (Px[i] - Px[j]) + (Py[i] - Py[j]) * (Py[i] - Py[j]));				if (distance < 10 || distance > 1000)    continue;				add(i + 1, j + 1, distance);				add(j + 1, i + 1, distance);			}		}		if (prime(1)) {   			printf("%.1f\n", ans * 100);		}		else {   			puts("oh!");		}	}}