相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4773
神犇题解：http://www.cnblogs.com/lytccc/p/6616625.html
解题报告
我们可以使用倍增Floyd来解决这个问题
具体来讲：
我们从大到小维护走$2^k$步后的最短路
如果出现负环，那么不继承，舍弃掉更改
如果没有出现负环，那么更新数组
时间复杂度：$O(n^3 \log n)$
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4773
神犇题解：http://www.cnblogs.com/lytccc/p/6616625.html
我们可以使用倍增Floyd来解决这个问题
具体来讲：
我们从大到小维护走$2^k$步后的最短路
如果出现负环，那么不继承，舍弃掉更改
如果没有出现负环，那么更新数组
时间复杂度：$O(n^3 \log n)$
Can I just say what a relief to find someone who actually knows what theyre talking about on the internet. You definitely know how to bring an issue to light and make it important. More people need to read this and understand this side of the story. I cant believe youre not more popular because you definitely have the gift.
You can definitely see your enthusiasm in the work you write. The arena hopes for more passionate writers such as you who aren’t afraid to mention how they believe. Always follow your heart.