甚至跑到了 2s，什么原理？

#include <bits/stdc++.h>
int n, siz[2005], fa[2005], val[2005], vis[2005];
typedef long long ll;
ll f[2005][2005];
int main(){
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= i; ++j){
      scanf("%lld", &f[i][j]);
      f[j][i] = f[i][j];
    }
  for(int i = 1; i <= n; ++i) siz[i] = 1;
  for(int i = 1; i <= n - 1; ++i){
    int mi = 0;
    for(int j = 1; j <= n; ++j)
      if(!vis[j] && (!mi || f[1][j] < f[1][mi]))
        mi = j;
    int im = 0;
    for(int j = 1; j <= n; ++j)
      if(!vis[j] && j != mi && (!im || f[mi][j] > f[mi][im]))
        im = j;
    //printf("round %d : %d %d\n", i, mi, im);
    long long delta = f[mi][mi] - f[mi][im];
    val[mi] = (int)(delta / (1ll * (n - siz[mi])));
    fa[mi] = im;
    vis[mi] = 1;
    siz[im] += siz[mi];
  }
  for(int i = 2; i <= n; ++i) printf("%d %d %d\n", fa[i], i, val[i]);
  return 0;
}