传送门

算法

枚举+构造。

不难发现，$M[i][j]$表示的就是i到j的最短路径。

那么先建一颗$1-2$的树，然后把$3-n$依次加入。
对于第$i$个节点，枚举它之前的所有节点，使所有的非叶子节点尽可能地靠近叶子节点，远离根节点，使公共部分尽量多。

这话有点抽象，我们来具体看看。
画个图就能发现，把节点$i$设为$1-j$路径上分出来的点，则多出来的长度为$(d[1][i]+d[j][i]-d[1][j])/2$。
这个应该很好理解。

那么每次找一个最小的加入就好了。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
int g[50][50];
int main() {
    int n;
    do {
        n=read(); if (n==0) break;
        for (re int i=1;i<=n;i++)
            for (re int j=i+1;j<=n;j++)
                g[i][j]=g[j][i]=read();
        int ans=g[1][2];
        for (re int i=3;i<=n;i++) {
            int now=2147483647;
            for (re int j=1;j<i;j++)
                now=min(now,(g[1][i]+g[i][j]-g[1][j])/2);
            ans+=now;
        }
        printf("%d\n",ans);
    } while (n!=0);
    return 0;
}