通电
作者:
不知名的fE
,
2025-02-02 19:59:45
,
所有人可见
,
阅读 2
import java.util.*;
public class Main {
static final int N = 1010, INF = 0x3f3f3f3f;
static double[] dist = new double[N];
static boolean[] vis = new boolean[N];
static ArrayList<Pair> vs = new ArrayList<>();
static ArrayList<ArrayList<Pair>> head = new ArrayList<>();
static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0; i <= n; i++) {
head.add(new ArrayList<>());
}
for (int i = 1; i <= n; i++) {
vs.add(new Pair(sc.nextInt(), sc.nextInt(), sc.nextDouble()));
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
double dist = getDist(vs.get(i - 1), vs.get(j - 1));
add(i, j, dist);
add(j, i, dist);
}
}
prim(1);
}
static void prim(int start) {
Arrays.fill(dist, INF);
dist[start] = 0;
PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> Double.compare(a.z, b.z));
pq.add(new Pair(start, 0));
int cnt = 0;
double ans = 0;
while (!pq.isEmpty()) {
Pair cur = pq.poll();
int x = cur.x;
if (vis[x]) continue;
vis[x] = true;
cnt++;
ans += cur.z;
if (cnt == n) {
break;
}
for (Pair to : head.get(x)) {
int v = to.x;
double w = to.z;
if (dist[v] > w) {
dist[v] = w;
if (!vis[v])
pq.add(new Pair(v, w));
}
}
}
System.out.printf("%.2f", ans);
}
static void add(int x, int y, double z) {
head.get(x).add(new Pair(y, z));
}
static double getDist(Pair o1, Pair o2) {
double x = o1.x - o2.x;
double y = o1.y - o2.y;
double z = o1.z - o2.z;
return Math.sqrt(x * x + y * y) + z * z;//题目显示有误
}
}
class Pair {
int x, y;
double z;
public Pair(int x, double z) {
this.x = x;
this.z = z;
}
public Pair(int x, int y, double z) {
this.x = x;
this.y = y;
this.z = z;
}
}