最短路之Floyd算法

参考Floyd算法
弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。与其他最短路算法比较，floyd算法更为简洁，一般只需要五行。并且它可以解决多源最短路径问题。其复杂度为$O(n^3)$

模板

void floyd()
{
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        if(mat[i][j] > mat[i][k] + mat[k][j])
        {
            mat[i][j] = mat[i][k] + mat[k][j];
            p[i][j] = p[i][k] + p[k][j]; //p[i][j]记录从i到j经过的第一个节点
        }

    }
}