Lightoj 1094 - Farthest Nodes in a Tree

http://lightoj.com/volume_showproblem.php?problem=1094

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define N 30010
4. #define dbg printf("comes here\n");
5. vector<int> adj[N];
6. vector<int> weight[N];
7. int n;
8. bool visited[N];
9. int dis[N];
10. int node1, node2, di;
11. void show(){
12.     for(int i = 0; i <n; i++){
13.         for(int j = 0; j <= adj[i].size(); j++) cout<<adj[i][j]<<" ";
14.         cout<<endl;
15.         for(int j = 0; j <= weight[i].size(); j++) cout<<weight[i][j]<<" ";
16.         cout<<endl;
17.     }
18. }
19. void clr(){
20.     node1 = node2 = -1;
21.     di = 0;
22.     for(int i = 0; i <= n; i++){
23.         adj[i].clear();
24.         weight[i].clear();
25.         visited[i] = false;
26.         dis[i] = INT_MAX;
27.     }
28. }
29. void clrsome(){
30.     di = 0;
31.     for(int i = 0; i <= n; i++) {dis[i] = INT_MAX; visited[i] = false;}
32. }
33. void bfs(int source){
34.     list<int>q;
35.     q.push_back(source);
36.     visited[source]= true;
37.     dis[source] = 0;
38.     while(!q.empty()){
39.         int from = q.front();
40.         visited[from] = true;
41.         q.pop_front();
42.         for(int i = 0; i <adj[from].size(); i++){
43.             int to = adj[from][i];
44.             if(visited[to]) continue;
45.             q.push_back(to);
46.             dis[to] = min(dis[to],dis[from] + weight[from][i]);
47.             if(dis[to]>= di) {node1 = to; di = dis[to];}
48.         }
49.     }
50. }
51.  
52. int main(){
53.     int ts;
54.     scanf("%d", &ts);
55.     for(int c = 1; c <= ts; c++){
56.     scanf("%d", &n);
57.     clr();
58.     for(int i = 0; i <n-1; i++){
59.         int a, b, w;
60.         scanf("%d%d%d", &a, &b, &w);
61.         adj[a].push_back(b);
62.         adj[b].push_back(a);
63.         weight[a].push_back(w);
64.         weight[b].push_back(w);
65.     }
66.     //show();
67.     bfs(0);
68.     int first = node1;
69.     //cout<<"here to";
70.     //for(int i = 0; i <n; i++) cout<<dis[i]<<" ";
71.     clrsome();
72.     bfs(first);
73.     printf("Case %d: %d\n", c, di);
74.     //for(int i = 0; i <n; i++) cout<<dis[i]<<" ";
75.     //cout<<"distance = "<<di;
76.     }
77.     return 0;
78. }