每日一题：滑雪与时间胶囊（最小生成树）

题意

给定一个 $n$ 个点 $m$ 条边图，只能从点权高的点走到低的，且可以不计路程的瞬移至之前走过的某个点，求经过最多点的最短路径。

solution

求经过最多点显然直接bfs，建图的时候建高到低的单向边即可，（值得注意的是，若点权相同，则为相互可达的，需要建双向边）。然后根据bfs遍历可以走到的点，将走过的边加入边集，建一个新图出来。为了使路径最短，考虑最小生成树，但需要满足题目的条件，因此我们对新的图进行排序，以高度为第一关键字从大到小排，再以路径长度为第二关键字从小到大排，这样可以保证点最多的同时路径最短。