문제
트리란 모든 정점이 연결 되어 있고 사이클이 존재하는 무방향 그래프다. 트리 내에서 한 정점에 대해, 다른 모든 정점에서 해당 정점까지의 최단거리의 합이 최소일 경우 해당 정점은 트리의 중앙이라고 한다.
위의 그림에서 5개의 정점으로 이뤄진 가중치를 가지는 트리가 있다. 여기서 정점 B의 경우 트리의 중앙이 되며, 다음과 같이 다른 모든 정점에서 B까지의 정점까지의 최단거리의 합이 22가 되며, 이는 가능한 경우 중 최소가 된다.
B-A = 2 B-D = 7 B-C = 1 B-E = 7 + 5 = 12 총합 = 2 + 1 + 7 + 12 = 22
가중치를 가지는 트리가 주어졌을 때 이의 중앙을 찾아 최단거리의 총합을 계산하는 프로그램을 작성하라.
입력
입력의 첫째 줄에는 정점의 개수 N (1≤N≤10,000) 이 주어진다. 그 다음 줄부터 N-1개의 줄에는 3개의 숫자 a, b, w가 주어지는데, 이는 a번 정점과 b번 정점 사이를 잇는 간선의 가중치가 w라는 것이다. a와 b는 0 이상 n-1 이하의 정수이며 w는 1 이상 100 이하의 정수다.
출력
입력에 대해 트리의 중앙에 대한 다른 모든 정점의 최단거리의 가중치의 합을 구하라.
예제 #1
5
0 1 2
1 2 1
1 3 7
3 4 5
22
예제 #2
6
0 1 1
1 2 4
2 3 1
3 4 4
4 5 1
21
태그
출처
ICPC INC 2007 H번
로그인해야 코드를 작성할 수 있어요.