#include <iostream> #include <cstdio> #include <climits> using namespace std; //floyd算法的实现,利用邻接矩阵存储 const int MAXN = 500 + 10; const int INF = INT_MAX; int graph[MAXN][MAXN]; int dis[MAXN][MAXN]; void Floyd(int n) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { for (int k = 1; k <= n; ++k) { dis[i][j] = min(dis[i][j], graph[i][k] + graph[k][j]); } } } return; } int main() { int n; while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { scanf("%d", &graph[i][j]); //输入矩阵 if (i == j) { dis[i][j] = 0; //初始化dis矩阵 } else { dis[i][j] = INF; } } } Floyd(n); for (int i = 1; i <= n; ++i) { for (int j = 1;j <= n; ++j) { printf("%d ", dis[i][j]); } printf("\n"); } } return 0; }