思路

考虑根据这个邻接矩阵，如何生成一棵树。 先将点$1-2$连边，并将距离算进最终答案，这样构成了一个只有两个节点的树。

见例图：（黑色为还未加入树中，　红色为加入了，　字母点为非叶子节点，数字点为叶子节点）

加入两个点$1-2$，最终答案加上($2 - Ａ - B - 1$)的长度

加入点$3$，最终答案再加上($A - C - D - 3$)的长度

加入点$4$，最终答案再加上($D - 4$)的长度

加入点$5$，最终答案加上($C - 5$)的长度

如此往复，最终加入全部的点

也就是每次加点的时候，只需要把它和最近的一个已经在树上的点相连即可。这条路径的长度需要加入最终答案。

难点在于，如何确定每次加点需要累计的答案。离当前待加入的点　最近的一个树中点一定不是一个叶子节点，

但是我们只有每个叶子节点之间的最短距离。

观察下图

$1 ,2$都已经在树中了，$3$不在树中，要在最终答案中加入$A - 3$的长度，可以发现：

$$dis(A, 3) = (dis(2, 3) + dis(1, 3) - dis(1, 2)) / 2$$

也就是我们枚举两个在树中的点对，通过上面的式子，得到加入这个点的价值，这些价值中取最小值即可。

这样就可以算出答案。

我们按顺序加入点，如果当前要加入的点为点$i$，那就要考虑每一个已加入的点$1$-$(i - 1)$组成的点对。

同时可以发现，只需要从枚举$1$到剩余其他树中的点即可。

Codes

这题代码的话，我觉得唯一的难点在于如何读入……

/*!
 * Copyright(c) 2019 Shu_Yu_Mo
 * MIT Licensed
 * Luogu: https://www.luogu.org/space/show?uid=44615
 * Github: https://github.com/oldsuold/
 * Gitee: https://gitee.com/Shu_Yu_Mo/
 */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#define inf 0x7fffffff
#define _R register
using namespace std;
const int _ = 110;
inline int read()
{
    char c = getchar(); int sign = 1; int x = 0;
    while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } 
    while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
    return x * sign;
}
int M[_][_];
int n;
void doit()
{
    memset(M, 0, sizeof(M));
    for(_R int i = 1;i <= n;i++){
        for(_R int j = 1;j <= n - i;j++){
            M[i][j + i] = M[j + i][i] = read();
        }
    }
    int ans = M[1][2];
    for(_R int i = 3;i <= n;i++){
        int TMP = inf;
        for(_R int j = 1;j < i;j++)
            TMP = min(TMP, ((M[1][i] + M[j][i] - M[1][j]) >> 1));
        ans += TMP;
    }
    printf("%d\n", ans);
}       
int main()
{
    while((n = read()) != 0) doit();
    return 0;
}