首先，肯定是要求一棵生成树。那么有些同学 我 在不看题的情况下 2min 背默了一遍 Kruskal 最小生成树模板，喜提十五个 WA。 仔细想想，就会知道反例了。比如对于这张图： 最小生成树会选取权值为 222 和 333 的边，而正解应为权值 222 和 444 的边，最小生成树肯定走不通了。 随后，我们发现了“单源最短路”这几个关键字，开始往 Dijkstra 身上想。首先，Dijkstra （或其它单源最短路算法）跑出来的所有路径合在一起是一棵树，证明显然。同时这也符合了题面的最短条件。于是开始改进 Dijkstra 算法。发现拓展节点的时候，把所经过的边记录下来，就形成最短路生成树 （可能这么叫吧）。于是套一下模板就好了。 不开 ____ ____ 见祖宗。 双倍经验：ABC252E

第五题 - A24634.道路削减 题目链接跳转：A24634.道路削减 > 前言：刚开始看这道题目的时候看成了最小生成树的模板题目，盲目的 wsq 随手打了一篇最小生成树的代码交上去，荣获满堂红（葬送了好多次提交记录，真是个悲惨的事情）。 最短路树的模板题目，在 Dijkstra 求最短路径的基础上，记录每一个顶点的“前驱边”就行了。更进一步地，如果松弛了某一条边 E(A,B)E(A, B)E(A,B)，可以使得从源点到达 BBB 点的最短距离缩短，那么就保留这一条边（覆盖掉原本通往 BBB 点的前驱边即可，一开始没有可以设置为无穷大或者是一个无意义的数字）。可以证明，如果有 NNN 个顶点，排除源点，当每一个顶点都有一个前驱边时，图上正好只有 N−1N-1N−1 条边。且每一个点到源点的距离都是最小的。 PS：本题的数据量比较大，一定要开 long long 数据类型，同时在计算最短路初始化的时候，切记无穷大要开的大一点。 本题的 AC 代码如下：

题目解析 令 DiD_iDi 为从城市 111 到城市 iii 的最短距离。无论选择哪些道路，显然有 di≥Did_i\geq D_idi ≥Di 。 所以如果有选择道路的方案使得 di=Did_i=D_idi =Di 成立，那么这就是最优解。事实上，这样的选择方法总是存在的。 对于每个 i=2,3,…,Ni=2,3,\ldots,Ni=2,3,…,N，只需保留 “从城市 111 到城市 iii 的最短路径中的最后一条道路” 即可。 答案可以通过记录 Dijkstra\tt{Dijkstra}Dijkstra 算法中到达每个城市前的最后一条道路来找到。 AC代码 C++ AC代码： Python AC代码： 复杂度分析 使用 Dijkstra\tt{Dijkstra}Dijkstra 算法求最短路，并在过程中记录路径，时间复杂度为 O(Mlog⁡M)\mathrm{O}(M \log{M})O(MlogM)。

Dijkstra