Table of contents

• Problem
• Computational complexity
• Solution

# Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_A

# Computational complexity

$O(V)$

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define N_MAX 100001

typedef struct Edge { Int v, w; }Edge;

Int N;
Int d[N_MAX];
vector<Edge> edges[N_MAX];


Int bfs(Int u) {
    loop(i,0,N) {
        d[i] = -1;
    }
    
    queue<Int> Q;
    
    Q.push(u);
    d[u] = 0;
    
    while (!Q.empty()) {
        Int parent = Q.front(); Q.pop();
        for (auto child: edges[parent]) {
            if (d[child.v] != -1) continue;
            Q.push(child.v);
            d[child.v] = d[parent] + child.w;
        }
    }
    
    Int maxIndex = 0;
    loop(i,1,N) {
      if (d[maxIndex] < d[i]) maxIndex = i;
    }
    
    return maxIndex;
}


Int diametar() {
  Int u = bfs(0);
  Int v = bfs(u);
  return d[v];
}

int main(void) {
  Int u, v, w;
  cin >> N;
  while (cin >> u >> v >> w) {
    edges[u].push_back({v, w});
    edges[v].push_back({u, w});
  }
  
  cout << diametar() << endl;
}