构造树——高级

 1 Sec 64 MB |  显示标签
03
通过提交

题目描述

有一系列的点,满足任意两个点编号i yj。现在为了把这些点连起来,我们需要构建一颗有向的树,树的边都是向右或者向上,即沿着x轴或者沿着y轴。
下面就是一个样例。

写一个程序,找到可以连接所有点的树,是的树的所有边长度之和最小。

输入格式

第一行一个整数n (1 <= n <= 1000)表示点的个数。
接下来n行,每行两个整数xi,yi(0 <= xi, yi <= 10000)表示第i个点的坐标,且符合题目描述的要求。

输出格式

输出可以连接所有点的树的边之和的最小长度。

样例输入 #1

5
1 5
2 4
3 3
4 2
5 1



1
10000 0

样例输出 #1

12



0

 上传者
coach
 创建时间
2012-11-13 12:22