폭설이 밀라노 시를 덮어 도로로 이동할 수 없게 되자 밀라노 시장은 눈을 치워야 하는 도로의 목록을 추려냈습니다. 결과적으로 눈을 치우게 되는 도로의 수는 가능한 한 적지만 모든 두 교차로를 왕래할 수 있는 경로가 있도록 도로들이 선택됩니다. 눈을 치우는 작업은 교차로 중 한 곳에 있는 제설차 한 대와 운전자 Mirko씨가 진행하게 됩니다.
제설차는 미터당 1 리터의 연료를 소모하며, 목록에 있는 모든 거리를 최소한의 연료를 이용해 청소하고자 합니다. 모든 거리의 눈이 치워지면 제설차를 그 자리(마지막으로 방문하게 되는 교차로)에 주차하게 됩니다.
제설차가 소비할 연료의 총량을 계산하는 프로그램을 작성하십시오.
입력
첫 번째 줄에는 두 정수 N과 S (1 ≤ N ≤ 100000, 1 ≤ S ≤ N)가 주어집니다. N은 교차로의 개수, S는 제설차가 현재 위치한 교차로의 번호입니다. 교차로는 1부터 N의 자연수로 표현됩니다.
다음 N-1개 줄에 걸쳐 각각 세 정수 A, B, C가 주어집니다. A와 B 교차로 사이에 거리 C미터의 도로가 있음을 의미합니다.
qvixnh22 3년 전
문제
도시는 교차로와 교차로를 연결하는 도로로 구성되어 있습니다.
폭설이 밀라노 시를 덮어 도로로 이동할 수 없게 되자 밀라노 시장은 눈을 치워야 하는 도로의 목록을 추려냈습니다. 결과적으로 눈을 치우게 되는 도로의 수는 가능한 한 적지만 모든 두 교차로를 왕래할 수 있는 경로가 있도록 도로들이 선택됩니다. 눈을 치우는 작업은 교차로 중 한 곳에 있는 제설차 한 대와 운전자 Mirko씨가 진행하게 됩니다.
제설차는 미터당 1 리터의 연료를 소모하며, 목록에 있는 모든 거리를 최소한의 연료를 이용해 청소하고자 합니다. 모든 거리의 눈이 치워지면 제설차를 그 자리(마지막으로 방문하게 되는 교차로)에 주차하게 됩니다.
제설차가 소비할 연료의 총량을 계산하는 프로그램을 작성하십시오.
입력
첫 번째 줄에는 두 정수 N과 S (1 ≤ N ≤ 100000, 1 ≤ S ≤ N)가 주어집니다. N은 교차로의 개수, S는 제설차가 현재 위치한 교차로의 번호입니다. 교차로는 1부터 N의 자연수로 표현됩니다.
다음 N-1개 줄에 걸쳐 각각 세 정수 A, B, C가 주어집니다. A와 B 교차로 사이에 거리 C미터의 도로가 있음을 의미합니다.
출력
모든 거리를 청소하는 데 필요한 연료의 최솟값을 출력합니다.