这个屌丝很懒，什么也没留下！

[USACO Jan09]安全路径Safe Travel解题报告_usaco safe travel

作者：思考机器 | 2024-01-30 13:42:36

usaco safe travel

首先把最短路径树画出来（由题意最短路径唯一，所以是树）：

其中1是根。我们将树记作T，i的子树记作B。图中，B是绿色点，T-B是红色点。

而1~i最短路上的最后一条边（也就是不能走的边）即i的父亲边。将这条边去掉以后，1~i的最短路长什么样呢？

可以发现，一定是这样的：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/46715