题意: 告诉图中任意两点最短路,求所有路之和。
显然
#include <bits/stdc++.h>
using namespace std;
int dis[35][35];
int main()
{
int n;
while(scanf("%d",&n)&&n){
for(int i=1;i<=n-1;i++){
for(int j=i+1;j<=n;j++){
scanf("%d",&dis[i][j]);
}
}
int ans = dis[1][2];
int tmp;
for(int i=3;i<=n;i++){
tmp = 0x7fffffff;
for(int j=1;j<i;j++){
tmp = min(tmp, (dis[1][i]+dis[j][i] - dis[1][j])/2 );
}
ans+=tmp;
}
printf("%d\n",ans);
}
return 0;
}