[理工] floyd warshall计算！ Aa841018 PTT批踢踢实业坊

[理工] floyd warshall计算！

楼主: Aa841018 (andrew) 2019-12-14 21:46:53

https://i.imgur.com/WV2F6Qb.jpg
请教一下，各位在做类似交大这种5*5、6*6的floy warshall 算法时，都是硬干吗？
这题我20分钟做不完…
这题真的太夸张，有些是5*5也是要很久，如果是求transitive closure，那只有0、1可
以快很多，那还好，像交大这题…根本不可能在30分钟内做完吧？
有什么方法可以加速运算时间吗？（除了k列k行和上个矩阵相同这个以外）

作者: mi981027 (呱呱竹) 2019-12-14 22:04:00

这题因为他终点都是F 所以其实可以把所有边reverse然后用bellman ford算F到各点的距离会快一点

作者: DLHZ ( ) 2019-12-14 22:43:00

长知识感觉很好用

作者: mistel (Mistel) 2019-12-14 22:56:00

原来有这招

继续阅读

[理工] 104中央数学ponwar87123 [理工] 105 成大资演 SMMHpyramidinc [理工] 中央108计算机组织与作业系统ponwar87123 [理工] OS 2题！Aa841018 [理工] 108 成大线代pyramidinc [理工] 计组 GPU 多核心mistel [理工] 资演 101交大 12题递回和复杂度ching4562 [理工] 资结 hashingching4562 [理工] 105 交大资演pyramidinc [理工] 108中央资演对答案ponwar87123