说是图论，其实并不是标准的图论题呢。
传送门：GO
一开始完全没看懂如何完成，一看题解，顿悟这道题的精髓。
首先考虑到最简单的两个点1,2，ans=dis(1,2).
如果从i,j之间衍生出一条边，连向另外一点3，则有
ans=dis(1,2)+(dis(1,3)+dis(2,3)-dis(1,2))/2
如果再从2，3中衍生出一点4呢？
ans有两种情况：
1.ans=(dis(1,4)+dis(2,4)-dis(1,2))/2
2.ans=(dis(1,4)+dis(3,4)-dis(1,3))/2
实际上我们只用求延伸出的一段，其余的部分我们在之前就会求出来，所以那一段一定是最小的那一段。
所以列出一个公式：
（图片来源于Mathison的博客：GO）
之后就可以打代码AC了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 int x=0,f=1; 5 char c=getchar(); 6 while(!isdigit(c)){ 7 if(c=='-') f=-1; 8 c=getchar(); 9 } 10 while(isdigit(c)){ 11 x=(x<<1)+(x<<3)+(c^48); 12 c=getchar(); 13 } 14 return x*f; 15 } 16 int n,ans,now; 17 int dis[40][40]; 18 int main(){ 19 while(1){ 20 n=read(); 21 if(!n) break; 22 for(int i=1;i<n;i++){ 23 for(int j=i+1;j<=n;j++){ 24 dis[i][j]=dis[j][i]=read(); 25 } 26 } 27 ans=dis[1][2]; 28 for(int i=3;i<=n;i++){ 29 now=1e9; 30 for(int j=2;j<i;j++){ 31 now=min(now,(dis[1][i]-dis[1][j]+dis[i][j])>>1); 32 } 33 ans+=now; 34 } 35 printf("%d\n",ans); 36 } 37 return 0; 38 }