Advertisement
Guest User

Untitled

a guest
Nov 16th, 2019
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define forsn(i, s, n) for(int i=s;i<int(n);i++)
  6. #define forn(i, n) forsn(i, 0, n)
  7. #define all(v) v.begin(), v.end()
  8. #define NACHO ios_base::sync_with_stdio(0);cin.tie(NULL);
  9.  
  10. vector<bool> visited;
  11.  
  12. void dfs(int node, vector<vector<pair<int,int>>> &adj, vector<int> &dist){
  13.     visited[node] = 1;
  14.     for(auto u : adj[node]){
  15.         if(!visited[u.first]){
  16.             dist[u.first] = dist[node]+u.second;
  17.             dfs(u.first, adj, dist);
  18.         }
  19.     }
  20. }
  21.  
  22. int main(){
  23.     //ifstream cin("puesto.in");
  24.     //ofstream cout("puesto.out");
  25.     int m; cin >> m;
  26.     vector<vector<pair<int,int>>> adj (300001);
  27.     forn(i, m){
  28.         int u, v, w; cin >> u >> v >> w;
  29.         u--; v--;
  30.         adj[u].push_back({v, w});
  31.         adj[v].push_back({u, w});
  32.     }
  33.     visited.resize(300001, 0);
  34.     vector<int> dist (300001, 0);
  35.     dfs(0, adj, dist);
  36.     int nodito;
  37.     int maxi = 0;
  38.     forn(i, 300001){
  39.         if(dist[i] > maxi){
  40.             maxi = dist[i];
  41.             nodito = i;
  42.         }
  43.     }
  44.     visited.resize(300001, 0);
  45.     dist.resize(300001, 0);
  46.     dfs(nodito, adj, dist);
  47.     maxi = 0;
  48.     forn(i, 300001){
  49.         maxi = max(maxi, dist[i]);
  50.     }
  51.     printf("%.1f\n", maxi/2.0);
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement