这个周末很颓废，几乎什么也没干。谴责一下自己。
题目:http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1036
这题就是要求一个稠密图上的最小生成树，并且求在这个生成树上的一个点，要求这个点到其余所有点的距离和最小。题目条件保证生成树唯一。
解法：首先求最小生成树，用prim。每加入一个新的节点时，计算这个点到已经加入的所有点的距离。因为最小生成树中任意亮点的通路唯一，因此可以直接与prim中pre数组中的点到其余点做和求出。
代码:依然点击这里下载