《信息学奥赛一本通》解决最短路径问题（C++版本）

题目出处：《信息学奥赛一本通 （C++）版》P472页

线上OJ： 信息学奥赛一本通（C++版）在线评测系统

本题在书中被归类为 Floyed 问题，因此此处选择使用 Floyd 解法。Floyed 的时间复杂度为 O (N3)，适用于存在 负边权 的情形。

核心思想：

通过三层循环实现，

第一层循环用于遍历中间点 k，

第二层循环用于遍历起点 i ，

第三层循环用于遍历终点 j 。

该算法的原理较为直观：当点 i 到点 k 的路径长度与点 k 到点 j 的路径长度之和小于当前记录的点 i 到点 j 的路径长度时，则将该更短的路径长度作为新的记录值。用代码表达即为：

If (res[i][j] > res[i][k] + res[k][j]) res[i][j] = res[i][k] + res[k][j];

注：在初始化阶段存在一个实用技巧

若使用 int 类型数组，可以通过 memset(g, 0x3f, sizeof(g)) 将所有元素设置为一个极大值

若使用 double 类型数组