题库/G8021

#G8021. [GESP202606 八级] 线网建设

    传统题 难度: 普及 标签>GESPGESP八级最小生成树Prim欧氏距离浮点运算
时间限制1000 ms
内存限制512 MiB
通过率—0 / 0 次提交
题目描述 查看题解 开始编程Alt+E

G8021 · [GESP202606 八级] 线网建设

退出在线编程模式
普及 读懂题意,让每一次思考成为成长。
时间限制1000 ms
内存限制512 MiB
通过率—0 / 0 次提交

A 市有 nn 座基站需要通过线网互相连接。第 ii 座基站位于二维平面上坐标 (xi,yi)(x_i, y_i) 处。

第 ii 座基站与第 jj 座基站之间的距离定义为 (xi−xj)2+(yi−yj)2\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}。

如果两座基站之间的距离不超过给定的整数 ll,那么可以修建连接这两座基站的线路,线路长度为基站间的距离。

如果从一座基站出发,经过一系列线网中的线路可以到达另一座基站,则称这两座基站是互相连接的。

请问使得 nn 座基站两两之间都互相连接,需要修建的线路总长度最小是多少?如果不能修建满足条件的线网,则输出 Impossible。

输入格式

第一行,两个正整数 n,ln, l,分别表示基站数量与线路长度上限。

接下来 nn 行,每行两个整数 xi,yix_i, y_i,表示基站的坐标。

输出格式

输出一行。如果能修建满足条件的线网,则输出需要修建的最小线路总长度,保留两位小数。否则输出 Impossible。

4 2
1 0
-1 -1
0 0
1 1
3.41
4 1
1 0
-1 -1
0 0
1 1
Impossible

说明与数据范围

数据范围

对于 40%40\% 的测试点,保证 1≤n≤1001 \le n \le 100。

对于所有测试点,保证 1≤n≤5001 \le n \le 500,1≤l≤1001 \le l \le 100,−100≤xi,yi≤100-100 \le x_i, y_i \le 100。

来源与评测数据

GESP C++ 8级,2026年06月第1题。

本题含14个自行生成的测试点,非官方原版测试数据;每题总分100分。

题目信息

#821
—

暂无提交记录

练习难度 普及
时间限制
1000ms
内存限制
512MiB
上传者