poj3613Cow Relays (经过n条边的最短路)

poj3613Cow Relays (经过n条边的最短路)

//poj 3613
//求经过n条边的最短路
//此题让我更深入的了解了最短路的floyed算法
//首先对于一个图的可达矩阵A而言(可达为1，不可达为0)，A表示<i,j>是否直接可达。
//A*A表示<i,j>是否中间经过一个点k可达(因为是累加所有情况，只要有一个k可达，数字大于1，即为可达)。
//那么我们求的这个数字除了表示是否可达，有没有别的含义呢？
//在矩阵乘法过程中，我们做的累加实际上就是加法原理的累加，我们累加的结果是<i,j>的路径条数。
//对于<i,k>和<k,j>而言，假设<i,k>的路径条数为Aik,由于k-j是确定的，那么如果经过k到j就有Aik种可能性。那么是否可以经过k呢？取决于k-j是否有路，也就是Akj是否大于0.
//所以做了几次矩阵乘法，就相当于插入了几个点。//回到本问题
//如果事先定义最短路只有经过边才成立的话
//在邻接矩阵中dis[i][i]=INF;
//floyed的过程实际上是类似于矩阵乘法的,只不过加了个限制条件。(dis[i][j]=dis[i][k]+dis[k][j])
//我们既然可以用矩阵乘法模拟插入点的过程计算经过x条边的了路径条数，
//那么也可以用floyed乘法来模拟入点的过程计算经过x条边的了最短路径长度，
//一次floyed后所求的矩阵就是在i，j中插入一个点的k的最短路。
//用当前矩阵再进行floyed即，再向<i,j>中插入点k'，此时<i,j>中有两个点k,k'.在i，j中插入两个点的最短路。
//以前学的floyed更新最短路，虽然思想上是插入一个点，但是因为每次都只用dis一个数组，实际上更新过的点都会再次更新。
//我们每次都用新的数组，