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!");}}
}