Floyd算法（多源最短路）

求任意两点u，v之间的最短路径长度，时间复杂度是O（n^3），顶点数在200以内，邻接矩阵实现（方便）

Floyd算法描述：

枚举顶点k在1~n
以顶点k作为中介点，枚举所有顶点对i和j（i在1~n,j在1~n）
如果dis[i][k]+dis[k][j]<dis[i][j]成立
赋值 dis[i][k]+dis[k][j]=dis[i][j]

Floyd的核心代码：

void floyd(){
   
	int i,j,k;
	for(int k=1;k<=n;k++){
   
		for(int i=1;i<=n;i++){
   
			for(int j=1;j<=n;j++){
   
				if(map[i][k]!=inf&&map[k][j]!=inf&&map[i][j]>map[i][k]+map[k][j])
				map[i][j]=map[i][k]+map[k][j];
			}
		}
	}
}

题目链接：

哈利·波特的考试 (25分)