脚本宝典收集整理的这篇文章主要介绍了最短路径树 学习笔记，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

这大概是我自学的第二个这样的树模型了，第一个是 Kruskal 重构树。

最短路径树：一棵从固定的起点 (S) 作为根，建立节点数为 (n) 的树，满足 (S) 到 (i) 的简单路径为 (S) 到 (i) 的最短路。易知这样的树可能有很多棵，所以还要满足边权的总和最小。

求法其实很简单：按照跑最短路的实现（(mathrm {spfa/dijkstra})）（但是边权都为 (1) 可以用 (mathrm {bfs})，省去一个 (mathrm {LOG}) ），每次我们选择的边满足其在 (S-i) 的最短路中，且这个条件的当前边是满足上面条件的最小边。可以证明其满足定义。

例题：Edge Deletion。 建好最短路径树后，直接取 (k) 个点即可。（互相连通且与 (1) 联通） 注意 Dijkstra 的打法，打得不好很可能一个点的入边会被计算两次。

CF1005F Berland and the Shortest Paths 也是比较明显，算每个点当前有多少种方案选边使得形成最短路（跑Dijkstra时），用个 vector 存边，最后乘起来比较后 DFs 随便选即可。

脚本宝典总结

以上是脚本宝典为你收集整理的最短路径树 学习笔记全部内容，希望文章能够帮你解决最短路径树 学习笔记所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。