\(md\) 怎么今天写一个题就遇到一个没学过的知识点？我真的什么都没学过吗？？？
最短路径树是一棵树，满足 \(dis(u,root)\) 等于在原图中源点到 \(u\) 的最短路长度。
求这个很简单，也是直接 \(dij\) 就行了。
但是又要求这棵树边权和最小，于是有了一个贪心算法，即时地更新 \(pre\)。
感觉不太可贪，但细想感觉又没什么问题。
\(Easy\)，但是有点鸡肋。
这两天运气不好就当是为 \(NOIP\) 攒 \(RP\) 吧。
标签：知识点,没学过,原图,源点,路径,最短 From： https://www.cnblogs.com/yhy-trh/p/SBT.html