【基本思想】

Floyd 算法是基于动态规划思想的求解单源最短路的算法，其基本思想如下：

递推产生一个 $n$ 阶方阵序列：

$A^{(-1)},A^{(0)},..,A^{(k),..,A^{(n-1)}}$

其中 $A^{k}[i][j]$ 代表从点 $v_i$ 到点 $v_j$ 的路径长度，$k$ 为绕行第 $k$ 个顶点的运算步骤

初始时，对任意两点 $v_i$ 与 $v_j$，若它们间存在边，则以此边上的权值作为两点最短路；若他们间不存在边，以一个极大数 INF 作为两点最短路，代表不可达

之后，逐步尝试在原路径中加入点 $k$，作为中间结点，若增加中间结点后，新路径路径长度比原路径路径长度减小，则用新路径替代原路径，即：

$A^{k}[i][j]=min\{A^{k-1}[i][j],A^{k-1}[i][k]+A^{k-1}[k][j] \}$

【算法分析】

以下图为例

初始时，邻接矩阵为

$A^{(-1)}=\begin{bmatrix} 0 & 6 & 13 \\ 10 & 0 & 4 \\ 5 & INF & 0 \end{bmatrix}$

第一次选择 $0$ 号点作为中间结点，有：

$A^{(-1)}[2][1]>A^{-1}[2][0]+A^{-1}[0][1]=11$

令 $A^{0}[2][1]=11$，进行更新，更新后有：

$A^{(0)}=\begin{bmatrix} 0 & 6 & 13 \\ 10 & 0 & 4 \\ 5 & 11 & 0 \end{bmatrix}$

第二次选择 $1$ 号点作为中间结点，有：

$A^{(0)}[0][2]>A^{0}[0][1]+A^{0}[1][2]=10$

令 $A^{1}[0][2]=10$，进行更新，更新后有：

$A^{(1)}=\begin{bmatrix} 0 & 6 & 10 \\ 10 & 0 & 4 \\ 5 & 11 & 0 \end{bmatrix}$

第三次选择 $2$ 号点作为中间结点，有：

$A^{(1)}[1][0]>A^{1}[1][2]+A^{1}[2][0]=9$

令 $A^{2}[1][0]=9$，进行更新，更新后有：

$A^{(2)}= \begin{bmatrix} 0 & 6 & 10 \\ 9 & 0 & 4 \\ 5 & 11 & 0 \end{bmatrix}$

【实现】

#define INF 0x3f3f3f3f
int G[N][N];   //邻接矩阵
bool visit[N]; //访问数组
int main() {
    int n, m;
    scanf("%d%d", &n, &m); //n个点m条边
    
    //邻接矩阵初始化
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            G[i][j] = INF;
    
    //建图
    for (int i = 1; i <= m; i++) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        if (w < G[x][y]) {
            G[x][y] = w;
            G[y][x] = w;
        }
    }
    
    for (int k = 1; k <= n; k++) //枚举中间点
        for (int i = 1; i <= n; i++) //枚举起点
            for (int j = 1; j <= n; j++) //枚举终点
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
    
    printf("%d\n", G[1][n]); //从起点1到起点n的最短路长度
    return 0;
}