P1268-树的重量

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define pb push_back
 4 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 5 #define INF 100000003
 6 #define ll long long
 7 inline ll read()
 8 {
 9     ll ans = 0;
10     char ch = getchar(), last = ‘ ‘;
11     while(!isdigit(ch)) last = ch, ch = getchar();
12     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - ‘0‘, ch = getchar();
13     if(last == ‘-‘) ans = -ans;
14     return ans;
15 }
16 inline void write(ll x)
17 {
18     if(x < 0) x = -x, putchar(‘-‘);
19     if(x >= 10) write(x / 10);
20     putchar(x % 10 + ‘0‘);
21 }
22 int n;
23 int a[40][40];
24 int main()
25 {
26     while(~scanf("%d",&n))
27     {
28         if(!n)
29             break;
30         _for(i,1,n+1)
31             _for(j,1,n+1)
32                 if(i<j)
33                     a[i][j] = a[j][i] = read();
34         
35         
36         int ans = 0;
37         _for(i,3,n+1)
38         {
39             int t = INT_MAX;
40             _for(j,2,i)
41             {
42                 t = min(t,(a[1][i]+a[i][j]-a[1][j])/2);
43             }
44             ans += t;
45         }
46         printf("%d\n",ans+a[1][2]);
47     }
48     
49     return 0;
50 }