fork download
copy 
  1. #include<cstdio>
  2. #include<vector>
  3. #include<cstring>
  4. #include<queue>
  5. #include<map>
  6. #include<utility>
  7. #include<iostream>
  8. #define rl(x) scanf("%lld",&x)
  9. #define ll long long
  10. using namespace std;
  11. ll cou=0,x,c,w;
  12. #define pii pair<int,int>
  13. vector<pii>G[50005];
  14. int main()
  15. {
  16. 	ll t;
  17. 	rl(t);
  18. 	while(t--)
  19. 	{
  20. 	ll n,u,v,x,dis,res,m=0,ed;
  21. 	rl(n);
  22. 	ll vis[n+5];
  23. 	for(ll i=0;i<n-1;i++)
  24. 	{
  25. 		rl(u),rl(v),rl(w);
  26. 		G[u].push_back(pii(v,w));
  27. 		G[v].push_back(pii(u,w));
  28. 	}
  29. 	memset(vis,0,sizeof(vis));
  30. 	queue<pii>Q;
  31. 	Q.push(pii(1,0));
  32. 	vis[1]=1;
  33. 	while(!Q.empty())
  34. 	{
  35. 		 x=Q.front().first;
  36. 		for(ll i=0;i<G[x].size();i++)
  37. 		{
  38. 			ed=G[x][i].first;
  39. 			 c=G[x][i].second;
  40. 			if(!vis[ed])
  41. 			{
  42. 				vis[ed]=1;
  43. 				dis=Q.front().second+c;
  44. 				if(m<=dis)
  45. 				{		
  46. 					m=dis;
  47. 					res=ed;
  48. 				}
  49. 				//cout<<"pushing "<<ed<<" "<<dis<<endl;
  50. 				Q.push(pii(ed,dis));
  51. 			}
  52. 		}
  53. 		Q.pop();
  54. 	}
  55. 	//printf("res=%lld len=%lld",res,m);
  56. 	memset(vis,0,sizeof(vis));
  57. 	Q.push(pii(res,0));
  58. 	vis[res]=1;
  59. 	while(!Q.empty())
  60. 	{
  61. 		 x=Q.front().first;
  62. 		for(ll i=0;i<G[x].size();i++)
  63. 		{
  64. 			ed=G[x][i].first;
  65. 			c=G[x][i].second;
  66. 			if(!vis[ed])
  67. 			{
  68. 				vis[ed]=1;
  69. 				dis=Q.front().second+c;
  70. 				if(m<=dis)
  71. 				{		
  72. 					m=dis;
  73. 					res=ed;
  74. 				}
  75. 				//cout<<"pushing "<<ed<<" "<<dis<<endl;
  76. 				Q.push(pii(ed,dis));
  77. 			}
  78. 		}
  79. 		Q.pop();
  80. 	}
  81. 	printf("%lld\n",dis);
  82. 	for(ll i=1;i<=n;i++)
  83. 	G[i].clear();
  84. 	}
  85.  
  86. }
Success #stdin #stdout 0s 3408KB
comments ()
stdin
copy 
1
6
1 2 3
2 3 4 
2 6 2
6 4 6
6 5 5
stdout
copy 
12
https://ideone.com/avs8zS
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
public

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!