填空题
合并果子
发布于 2022-03-03 17:00:21
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了N堆。果园是一个二维平面，第i堆果子的位置为(Xi,Yi)，重量为Wi。
多多决定把所有的果子合成一堆。每一次合并，多多可以消耗Wi (|Xi - Xj |+|Yi - Yj |)的体力把第i堆果子合并到第j堆。可以看出，所有的果子经过N-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
请你求出将所有果子合并成一堆消耗的总体力最少是多少。
输入描述： 第一行一个正整数N，接下来N行每行三个正整数 Xi Yi Wi输入样例： 4 2 1 1 1 2 3 3 1 2 2 4 2 输出描述： 一个数，最少消耗的总体力输出样例 14关注者
0
被浏览
6
