本题洛谷题解区两篇题解的做法均是将所有点按最短路长度排序后 DP。但是需要注意的是这种做法正确的前提是：图中不存在零环。（这点可以做一下 P3953 [NOIP2017 提高组] 逛公园 体会一下）并且实际上本题中的建图方式比较特殊，不会存在零环。所以才可以直接排序而不采取进一步的处理手段（记忆化搜索 / 缩点）。