一些碎碎念
最近复习了一些简单图论的知识，主要有floyd，spfa，拓扑排序，dij，差分等等。其实真正意义上的算法就是floyd和dij以及拓扑排序（spfa目前的应用场景仅限于有负边的最短路，然而听说可能还打不过BF？我对此有点不信的）。下面记录一下最近做题时这些算法常见的技巧
floyd
对于第一次学习的人来说，它的正确性可能是显然的，但是并非所有人都真正明白它的正确性来自什么。比如，为什么三层循环的最外层枚举的是中转点？能不能交换三个变量的枚举顺序？答案是不能的。其原因在于，它的本质是一个dp。
rep(k,1,n)
rep(i,1,n)
rep(j,1,n){
f[i][j]=min(f[i][j],f[i][k]+f[k][j])
}
对于以上的代码，f的意思应该是：当从i到j的路径中的点的最大标号不超过当前的k时能获得的最短路。换而言之，枚举k的本质是尝试向一个集合
思路
代码