AOJ

# # Problem

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

# # Computational complexity

$O(V)$

# # Solution


#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;
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!