ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#10419

흥미로운 나들이 10s 1024MB

問題

당신은 외지에서 온 손님들을 맞이하고 있으며, 그들을 데리고 나가 도시에서 가장 흥미로운 장소들을 보여주고 싶다.

관광하고 싶은 흥미로운 명소가 \mathbf{N}개 있다. 당신은 이동 수단을 \mathbf{N}-1개 찾아냈는데, 각 이동 수단은 두 명소를 양방향으로 연결한다. 다행히도, 어떤 흥미로운 명소에서 다른 명소로 갈 때 어떤 이동 수단도 두 번 이상 사용하지 않는 경로는 정확히 하나뿐이다.

당신은 각 이동 수단을 한 번 사용할 때(사용할 때마다 비용을 지불한다) 손님 일행에게 드는 비용을 알고 있다. 당신은 여행의 시작 명소와 끝 명소를 정할 수 있으며, 둘은 같은 명소일 수도 있고 서로 다른 명소일 수도 있다. 시작 지점까지 이동하거나 끝 지점에서 돌아오는 비용은 고려하지 않아도 된다. 여행 중 명소들 사이를 이동하는 데 드는 비용만 고려하면 된다. 모든 명소를 최소 한 번씩 방문하기 위한 최소 비용은 얼마인가?


入力

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 정수 \mathbf{N}이 주어진 한 줄로 시작하며, 이는 방문하고 싶은 명소의 개수이다. 그 다음 \mathbf{N}-1줄이 이어진다. 이 중 i번째 줄에는 세 정수 \mathbf{A_i}, \mathbf{B_i}, \mathbf{C_i}가 주어진다. 이는 i번째 이동 수단을 이용하면 명소 \mathbf{A_i}에서 명소 \mathbf{B_i}로 또는 명소 \mathbf{B_i}에서 명소 \mathbf{A_i}로 이동할 수 있으며, 사용할 때마다 비용이 \mathbf{C_i} 코인 든다는 뜻이다.


出力

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 각 명소를 최소 한 번씩 방문하는 여행의 최소 비용이다.


例題 

3
6
1 3 10
4 5 10
3 4 10
4 6 20
2 3 30
6
1 3 35
4 5 10
3 4 10
4 6 20
2 3 30
5
1 3 1000000000
2 3 1000000000
3 4 1000000000
3 5 1000000000
Case #1: 100
Case #2: 145
Case #3: 6000000000
샘플 케이스 #1에서는(아래 그림 참조) 최적 경로가 그림의 빨간 선처럼 2, 3, 1, 3, 4, 5, 4, 6의 순서로 명소를 방문한다. 샘플 케이스 #2에서는(위 그림 참조) 샘플 케이스 #1과 비교해 명소 1과 3 사이의 이동 비용이 10에서 35로 비싸진 것뿐이다. 경로 2, 3, 1, 3, 4, 5, 4, 6은 이 경우 비용이 150이지만 최적이 아니다. 대신 최적 경로는 2, 3, 4, 6, 4, 5, 4, 3, 1이며(그림에서 빨간 선으로 표시됨), 이것이 최적이다. 샘플 케이스 #3에서는 답이 2^{32}보다 클 수 있음을 유의하라.

出典

GCJ 2022iow C

ログインしないとコードを書けません。