此笔记开始记录时间为2019.7.20
主要供自己深化知识点

一、Floyd算法：

流程（重点理解）：

通常我们写的Floyd算法框架是这样的

for(int k=1;k<=n;++k)
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

Floyd算法能如此优美是由于其为dp算法
式子如此简单以至于我们能轻而易举将其背下
大部分人对其了解只限于——三重循环 k 放最外层 i j 放内层
但是这个算法并不是这么的显然
首先
说这是个dp算法
因为存在转移方程——d[i][j]=min(d[i][j],d[i][k]+d[k][j])
可以感性理解一下：
对不起我太菜了

稍稍证明一下：
设d[i][j][k]为i->j路径只经过1-k节点的最短路
且d[i][j][0]为i->j的初始路径
则若经过k节点
d[i][j][k]=d[i][k][k-1]+d[k][j][k-1]
否则
d[i][j][k]=d[i][j][k-1]
最后滚动数组就可以得出最终式了

严格证明
dp最初形式

用法总结：

1. 最短路：
   balabala
2. balabala:
   balabala