import sys
input = sys.stdin.readline
import heapq
INF = sys.maxsize
N = int(input())
graph = [[] for i in range(N+1)]
for i in range(N-1):
x1,x2,w = map(int,input().split())
graph[x1].append((x2,w))
graph[x2].append((x1,w))
hq = []
distance = [[-INF]*(N+1) for i in range(2)]
def Dijkstra(node,distance):
heapq.heappush(hq,(0,node))
while hq:
w,now = heapq.heappop(hq)
if distance[now] >= w:
continue
distance[now] = w
for i in graph[now]:
x,weight = i
heapq.heappush(hq,(w-weight,x))
Dijkstra(1,distance[0])
Dijkstra(1+distance[0][1:].index(min(distance[0][1:])),distance[1])
print(-min(distance[1][1:]))
다 익스트라 알고리즘으로 해결하였다. 아무 노드를 시작점으로 잡고 (보통 1), 해당 노드에서 가장 먼 노드를 찾고, 그 노드에서 가장 먼 노드를 찾아 거리를 구하면 그것이 곧 트리의 지름이다.
다익스트라 알고리즘은 최단거리를 찾도록 설계되어 있기에, heapq에 삽입할때 거리값을 음수로 넣어주어야 한다.
다 익스트라 알고리즘, 처음에 이와 관련된 문제를 보았을때는 풀이방법이 일주일 넘게 안떠올라 나를 끙끙대게 했었는데 (사실 지금 생각하면 안떠오르는게 당연하다) 알고 나면 너무나 편리한 알고리즘이 아닐 수 없다.
오늘의 교훈) 다 익스트라 알고리즘을 잘 활용하자