SZ#G8M26. 【GESP强化 八级】校园光缆铺设计划

提交1 通过1
通过率100%
时间限制2000ms
内存限制256MiB
    ID: 10852 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 普及 上传者: 标签>GESPGESP强化C++c++编程题最小生成树Kruskal距离平方

题目描述

珅泽教育准备升级校园网络,把分布在不同位置的若干场馆用光缆连接起来,使任意两个场馆之间都能通过光缆网络互相通信。每个场馆用平面上的一个点表示,两点之间铺设光缆的费用等于它们欧几里得距离的平方。

由于过短的线路无法满足施工规范,施工方只允许铺设费用不少于门槛 CC 的连接。刘老师希望在符合要求的连接中选择若干条,使全部场馆连通且总费用最低。请输出最低总费用;如果无论怎样选择都无法连通全部场馆,则输出 1-1

输入格式

第一行输入 n,Cn,C,随后 nn 行输入坐标 x,yx,y

输出格式

输出最低费用;无法连通输出 1-1

输入 #1

3 11
0 2
5 0
4 3

输出 #1

46

输入 #2

2 1
0 0
1 0

输出 #2

1

输入 #3

3 1000
0 0
1 1
2 2

输出 #3

-1

数据范围与约定

  • 2 ≤ nn ≤ 60
  • 0 ≤ xx,yy ≤ 1000
  • 1 ≤ CC ≤ 1000000