fork(3) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<pair<int , int> > G[50005];
  5.  
  6. int bfs1(int x){
  7. 	queue<pair<int , long long> > q;
  8. 	bool visited[50005];
  9. 	fill(visited,visited+50000,false);
  10. 	q.push(make_pair(x , 0));
  11. 	long long d=0 ; int node = x;
  12. 	pair<int , long long> temp;
  13. 	while(!q.empty()){
  14. 		 temp = q.front(); q.pop();
  15. 		 if(temp.second >= d) { d= temp.second ; node = temp.first; }
  16. 		 visited[temp.first]=1;
  17. 		for(auto i=G[temp.first].begin() ; i!=G[temp.first].end() ; i++){
  18. 			if(!visited[i->first]) q.push(make_pair(i->first , temp.second+i->second));
  19. 		}
  20. 	}
  21. 	return node;
  22. }
  23.  
  24. long long bfs2(int x){
  25. 	queue<pair<int , long long> > q;
  26. 	bool visited[50005];
  27. 	fill(visited,visited+50000,false);
  28. 	q.push(make_pair(x , 0));
  29. 	long long d=0 ; int node = x;
  30. 	pair<int , long long> temp;
  31. 	while(!q.empty()){
  32. 		 temp = q.front(); q.pop();
  33. 		 if(temp.second >= d) { d= temp.second ; node = temp.first; }
  34. 		 visited[temp.first]=1;
  35. 		for(auto i=G[temp.first].begin() ; i!=G[temp.first].end() ; i++){
  36. 			if(!visited[i->first]) q.push(make_pair(i->first , temp.second+i->second));
  37. 		}
  38. 	}
  39. 	return d;
  40. }
  41.  
  42. int main() {
  43. 	ios_base::sync_with_stdio(false);
  44. 	int t , n , a , b , c , x;
  45. 	cin>>t;
  46. 	while(t--){
  47. 		cin>>n;
  48. 		for(int i=0 ; i<=n ; i++) G[i].clear();
  49. 		for(int i=1 ; i<n ; i++){
  50. 			cin>>a>>b>>c;
  51. 			G[a].push_back(make_pair(b , c));
  52. 			G[b].push_back(make_pair(a , c));
  53. 		}
  54.  
  55. 		x = bfs1(2);
  56. 		cout<<bfs2(x)<<"\n";
  57. 	}
  58. 	return 0;
  59. }
Success #stdin #stdout 0s 3864KB
comments (?)
stdin 
2
6
1 2 1900
2 3 2600
2 6 2578
6 4 2579
6 5 3015
7
1 2 3
2 3 4 
2 6 2
6 4 6
6 5 5
1 7 15
stdout 
8193
26
https://ideone.com/93P0zF
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!