floyd算法，代码简介明了

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 55,inf=1e9+10;

int g[N][N], n;

void floyd()

{

    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]);

}

int main()

{

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)

    {

        for (int j = 1; j <= n; j++)

        {

            scanf("%d", &g[i][j]);

            if (g[i][j] == 0&&i!=j)

                g[i][j] =inf;

        }

    }

    floyd();

    for (int i = 1; i <= n; i++)

    {

        for (int j = 1; j <= n; j++)

        {

            if (i == j)

                g[i][j] = 0;

            if (g[i][j] > inf / 2)

                printf("-1 ");

            else

                printf("%d ", g[i][j]);

        }

         puts("");

    }

    puts("");

    return 0;

}