송전탑 네트워크 지름
골드 III의견: 0
전력 회사는 \(N\)개의 송전탑(번호 \(1\)부터 \(N\))을 \(N-1\)개의 송전선으로 연결하여, 전체가 하나로 이어진 트리 형태의 전력망을 만들었다. 각 송전선에는 전력 손실을 나타내는 양의 정수 가중치가 있다.
두 송전탑 사이의 거리는 두 탑을 잇는 유일한 경로상의 송전선 가중치 합으로 정의한다. 전력망 전체에서 가장 먼 두 송전탑 사이의 거리(즉 트리의 지름)를 구하여라.
\(1 \le N \le 200{,}000\). 입력으로 주어지는 그래프는 항상 하나로 연결된 트리이다.
첫째 줄에 송전탑의 수 \(N\)이 주어진다. 이어 \(N-1\)개의 줄에 각각 세 정수 \(a\), \(b\), \(w\)가 주어지며, 이는 송전탑 \(a\)와 \(b\)가 가중치 \(w\)인 송전선으로 연결됨을 뜻한다 (\(1 \le a, b \le N\), \(1 \le w \le 10^9\)).
트리의 지름(가장 먼 두 송전탑 사이의 거리)을 한 줄에 출력한다.
5
1 2 3
2 3 4
2 4 2
4 5 6
12탑 3에서 탑 5까지의 경로는 \(3\to2\to4\to5\) 로 거리 \(4+2+6=12\) 이며, 이것이 전체에서 가장 먼 두 탑 사이의 거리이다.
2
1 2 7
7탑이 둘뿐이므로 지름은 두 탑 사이의 가중치 7이다.
riseoj 작성
출처 Original
평가 및 의견
송전탑 네트워크 지름
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
송전탑 네트워크 지름