트리끊기 > 문제은행



문제은행

1469 : 트리끊기

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 6 회    시도횟수: 10 회   



트리(사이클이 존재하지 않는 무방향 그래프) 형태의 그래프가 주어져 있다. 트리를 이루는 간선에는 가중치가 주어진다.

 

root 노드(부모 노드가 존재하지 않는 노드)에서 모든 leaf 노드(자식 노드가 존재하지 않는 노드)로 도달하지 못 하게 만들기 위해서 지우게 되는 간선의 가중치의 합의 최소는 얼마인지 알아보는 프로그램을 작성하라.




입력의 첫 번째 줄에는 노드의 개수와 root 노드 번호를 뜻하는 N(1≤N≤1,000, 1≤R≤1,000)가 입력되며 N-1개의 줄에는 간선들의 정보가 주어진다.
간선들의 정보는 세 개의 정수 A, B, C(1≤A, B, C≤1000)이뤄져 있으며 A번 노드와 B번 노드 사이에 가중치가 C인 간선이 존재한다는 것이다.



끊게 되는 간선들의 가중치의 합의 최소를 출력한다.


4 1 
1 2 3 
2 3 1 
3 4 3
1


15 15 
1 2 1 
2 3 2 
2 5 3 
5 6 7 
4 6 5 
6 7 4 
5 15 6 
15 10 11 
10 13 5 
13 14 4 
12 13 3 
9 10 8 
8 9 2 
9 11 3
16



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.