Advertisement
GastonFontenla

Untitled

Nov 16th, 2019
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6.  
  7. struct arista
  8. {
  9.     int desde, hasta, costo;
  10. };
  11.  
  12. vector <vector <arista> > ady;
  13. vector <int> dist;
  14. vector <bool> visit;
  15.  
  16. void DFS(int n)
  17. {
  18.     visit[n] = true;
  19.     for(const auto &i:ady[n])
  20.     {
  21.         if(!visit[i.hasta])
  22.         {
  23.             dist[i.hasta] = dist[n]+i.costo;
  24.             DFS(i.hasta);
  25.         }
  26.     }
  27. }
  28.  
  29. int main()
  30. {
  31.     freopen("puesto.in", "r", stdin);
  32.     freopen("puesto.out", "w", stdout);
  33.  
  34.     int n;
  35.     cin >> n;
  36.  
  37.     ady.resize(300001);
  38.  
  39.     for(int i=0; i<n; i++)
  40.     {
  41.         int a, b, c;
  42.         cin >> a >> b >> c;
  43.         ady[a].push_back({a, b, c});
  44.         ady[b].push_back({b, a, c});
  45.     }
  46.  
  47.     dist = vector <int> (300001, 0);
  48.     visit = vector <bool> (300001, false);
  49.     DFS(1);
  50.     int maxNodo = 1;
  51.     for(int i=1; i<=300000; i++)
  52.         if(dist[i] > dist[maxNodo])
  53.             maxNodo = i;
  54.     dist = vector <int> (300001, 0);
  55.     visit = vector <bool> (300001, false);
  56.     DFS(maxNodo);
  57.     for(int i=1; i<=300000; i++)
  58.         if(dist[i] > dist[maxNodo])
  59.             maxNodo = i;
  60.  
  61.     printf("%.1f\n", dist[maxNodo]/2.0);
  62.  
  63.     return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement