在Floyd算法更新最短路径的同时，更新最短路径之和

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int num;
    cin>>num;
    int ans = 0;
    int ** mpt = new int* [num];
    for(int i = 0; i < num; i ++){
        mpt[i] = new int [num];
        for(int j = 0; j < num; j ++){
            cin>>mpt[i][j];
            if(i < j)
                ans += mpt[i][j] * i;
            else
                ans += mpt[i][j] * j;
        }
    }
    for(int k = num - 1; k >= 0; k --)
        for(int i = 0; i < num; i ++)
            for(int j = i + 1; j < num; j ++)
                if(mpt[i][j] > mpt[i][k] + mpt[k][j]){
                    int coef = min(i, k);
                    ans = ans - 2 * coef * (mpt[i][j] - mpt[i][k] - mpt[k][j]);
                    mpt[j][i] = mpt[i][j] = mpt[i][k] + mpt[k][j];                    
                }
    cout<<ans;
    return 0;
}