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