本题依然是MST的基本题，但是时间要求非常严格。对于Krusal算法而言，需要将所有的边进行排序。时间复杂度ElogE。本题中，任意两点之间都可能有路径，所以复杂度是N^2logN，对于不开o2优化的C++而言极有可能TLE。
降低TLE的方法有两个：
- 使用priority_queue而不是直接排序整个边长数组。原因是pq不会将所有装入其中的元素马上排序（建堆过程是o(E)），而是只有访问顶堆元素的时候才将最小值推出来。因为我们只需要找到N条边，数量级比N^2的总边数要少的多，所以可以省去不需要的排序过程。
- 避免使用vector（时空非常坑爹），改用定长数组array<int,N>这个数据结构。
Prim算法通常的复杂度也是ElogV，本题就是o(N^2logN)。
Prim的基本思想是，MST从节点0开始生长。MST里面只有节点0时，从所有节点0出发的边里面挑一个最短的，这时MST里就有两个点。第二步是从这两个点所出发的所有边里面挑一个最短的，如果对应的第三点是已经访问过的，那就换下一个最短边，直到能确定第三个点。依次继续，直至确定N个点，则MST构建完成。
同理，priority_queue的模板类尽量避免用vector。
在特殊情况下，Prim有o(N^2)的实现，那就是可以用邻接表来表示任意的边。这样对于稠密图而言，Prim的这种实现在时间上会有优势。
本题是个完全图，任意两点之间都有边，所以是可以有o(N^2)的实现，具体方法是：我们在构建MST的过程中收入了一个新点k，此时收录的点集是{q}. 查看所有未被收入的点pi到k点的距离，用来更新di，其中di就是pi到距离点集{q}最小的长度。这样我们就可以在{di}找到最小的那个，对应的点就是下一次要收入的新点k'. 因此这样的算法就不要使用priority_queue.