fork(3) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<pair<int,int> > adj[50000+5];
  4. pair<int,int> bfs(int x,int n){
  5.     bool vis[n+1];
  6.     int dist[n+1];
  7.     for(int i=0;i<=n;i++){
  8.         dist[i]=0;
  9.         vis[i]=false;
  10.     }
  11.     dist[x]=0;
  12.     queue<int>q;
  13.     q.push(x);
  14.     vis[x]=true;
  15.     while(!q.empty()){
  16.         int p=q.front();
  17.         q.pop();
  18.         for(int i=0;i<adj[p].size();i++){
  19.             int e=adj[p][i].first;
  20.             int w=adj[p][i].second;
  21.             if(!vis[e]){
  22.                 dist[e]=dist[p]+w;
  23.                 q.push(e);
  24.                 vis[e]=true;
  25.             }
  26.         }
  27.     }
  28.     int node,weight=0;
  29.     for(int i=1;i<=n;i++){
  30.         if(dist[i]>weight){
  31.             node=i;
  32.             weight=dist[i];
  33.         }
  34.     }
  35.     return make_pair(node,weight);
  36. }
  37.  
  38. int longestPath(int n){
  39.     pair<int,int> t1,t2;
  40.     t1=bfs(1,n);
  41.     t2=bfs(t1.first,n);
  42.     return t2.second;
  43. }
  44.  
  45. int main(){
  46.     int t;
  47.     cin>>t;
  48.     while(t--){
  49.         int n;
  50.         cin>>n;
  51.         for(int i=0;i<=n;i++)
  52.             adj[i].clear();
  53.         int a,b,l;
  54.         for(int i=0;i<n-1;i++){
  55.             cin>>a>>b>>l;
  56.             adj[a].push_back({b,l});
  57.             adj[b].push_back({a,l});
  58.         }
  59.         cout<<longestPath(n)<<endl;
  60.     }
  61.     return 0;
  62. }
Runtime error #stdin #stdout 0s 4396KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/1oyryy
language:
C++14 (gcc 8.3)
created:
6 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!