#Psmt19. 5.最小距离和
5.最小距离和
5.最小距离和
题目描述
有n个点,任意两点A,B的距离(A,B)=MIN{|XA-XB|,|YA-YB|,|ZA-ZB|}。
其中(XA,YA,ZA)是A的空间位置,而(XB,YB,ZB)是B的空间位置。现在需要建立n-1条道路,以使所有点直接或间接相通,并且使所建道路距离和最小。
输入格式
第一行:一个数整数代表点数。
第二行到n+1行:每行三个整数x,y,z,代表点的坐标。
不会出现重复的点。
输出格式
输出一个整数,表示最小距离。
数据范围
(原站未提供,导入后需人工补齐)
样例
3
-1 -1 -1
5 5 5
10 10 10
11
提示
对于50%的数据,保证n<=4000;
对于100%的数据,保证n<=100000,坐标在之间。