1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 #define N 30008
 8 
 9 struct node
10 {
11     int v, w, next;
12 }e[N*4];
13 
14 int n, cnt, maxx;
15 int Index;   // 写成index过不了lightoj=·=||
16 int head[N], dist[N];
17 
18 void addedge(int u, int v, int w)
19 {
20     e[cnt].v = v;
21     e[cnt].w = w;
22     e[cnt].next = head[u];
23     head[u] = cnt++;
24 }
25 
26 void dfs(int u, int w)
27 {
28     dist[u] = w;
29     if(w > maxx)
30     {
31         maxx = dist[u];
32         Index = u;
33     }
34     for(int i = head[u]; i != -1; i = e[i].next)
35     {
36         if(dist[e[i].v] == -1)
37         {
38             dfs(e[i].v, dist[u]+e[i].w);
39         }
40     }
41 }
42 int main()
43 {
44     int t, u, v, w, k = 1;
45 
46     scanf("%d", &t);
47 
48     while(t--)
49     {
50         cnt = maxx = 0;
51         memset(head, -1, sizeof(head));
52 
53         scanf("%d", &n);
54         n--;
55         while(n--)
56         {
57             scanf("%d%d%d", &u, &v, &w);
58             addedge(u, v, w);
59             addedge(v, u, w);
60         }
61         memset(dist, -1, sizeof(dist));
62         dfs(0, 0);
63         memset(dist, -1, sizeof(dist));
64         dfs(Index, 0);
65         printf("Case %d: %d\n", k++, maxx);
66     }
67     return 0;
68 }

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 
 6 using namespace std;
 7 
 8 #define N 30008
 9 
10 struct node
11 {
12     int v, w, next;
13 } e[N*2];
14 
15 int n, cnt, maxx;
16 int Index;
17 int head[N], dist[N], vis[N];
18 
19 void addedge(int u, int v, int w)
20 {
21     e[cnt].v = v;
22     e[cnt].w = w;
23     e[cnt].next = head[u];
24     head[u] = cnt++;
25 }
26 
27 void bfs(int u)
28 {
29     memset(vis, 0, sizeof(vis));
30     queue<int> Q;
31     Q.push(u);
32     vis[u] = 1;
33     dist[u] = 0;
34 
35     while(Q.size())
36     {
37         u = Q.front();
38         Q.pop();
39 
40         for(int i = head[u]; i != -1; i = e[i].next)
41         {
42             int v = e[i].v;
43             if(!vis[v])
44             {
45                 vis[v] = 1;
46                 dist[v] = dist[u]+e[i].w;
47                 if(dist[v] > maxx)
48                 {
49                     maxx = dist[v];
50                     Index = v;
51 
52                 }
53                 Q.push(v);
54             }
55         }
56     }
57 }
58 
59 int main()
60 {
61     int t, u, v, w, k = 1;
62     scanf("%d", &t);
63 
64     while(t--)
65     {
66         maxx = cnt = 0;
67         memset(head, -1,sizeof(head));
68 
69         scanf("%d", &n);
70         n--;
71 
72         while(n--)
73         {
74             scanf("%d%d%d", &u, &v, &w);
75             addedge(u, v, w);
76             addedge(v, u, w);
77         }
78         memset(dist, 0, sizeof(dist));
79         bfs(0);
80         bfs(Index);
81         printf("Case %d: %d\n", k++, maxx);
82     }
83     return 0;
84 }