H 如果我们把所有的点两两之间连边，题目很明显是找到该图的一个最小生成树。 现在我们需要减少边的数量。 首先容易想到当两个点之间的距离为 ,但两个点之间已经有一条简单路径长度为 ，且满足,则这条长度为的边是没有必要的。 考虑把所有点按排序，并在相邻的两点之间连边。 接着对进行同样的操作。 可以证明没有被连到的边不会产生比已有边更优的情况。 时间复杂度 #define int long long using namespace std; const int N=1e5+7,M=1e6; // const int p=998244353; const double eps=1e-9,pi=acos...