上海交大2019年机试第三题

floyd算法，调整了一下循环次序

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

int Floyd(int n) {
    int answer = 0;
    for (int k = n - 1; k >= 2; --k) {       //k表示剩下的第一个点,只对新增节点进行松弛操作
        for (int i = k; i <= n; ++i) {
            for (int j = k; j <= n; ++j) {
                dis[i][j] = min(dis[i][j], graph[i][k] + graph[k][j]);
                answer += dis[i][j];
            }
        }
    }
    return answer;
}

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;
                }
            }
        }
        printf("%d\n", Floyd(n));
    }
    return 0;
}