acm趣味题:
描述：
在二维坐标上给你m个点(m是偶数)的坐标,坐标都是整数,你可以任意联接其中两点(不管中间有没有障碍),这两点就消失了(和游戏里的一样).但消去两点的路径和两个点的位置有关,也就是说路径的长度等于两点x轴与y轴差的绝对值之和.比如一个点坐标为(10,10),另外一个点坐标为(2,3),那么消去这两个点的路径长度为8 7=15.问消去所有点的路径长度之和最小值是多少?
第一行输一个正整数n,下面有n种连连看的地图每种地图的第一行输入一个正整数m (m是偶数,并且2= < m <=20),代表地图上有m个点. 下面有m行,每一行都有两个整数,代表这个点的x轴坐标与y轴坐标. (坐标的绝对值不会大于十万)输出共n行,每行都是消去所有点的路径长度之和的最小值.
sample input 3
2 10 10 2 3
2 0 1 0 2
4 0 2 0 3 0 5 0 6
sample output 15 1 2