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

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

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

#10419 upload 1 done 1 how_to_reg 1

Interesting Outing timer 10s memory 1024MB

#10419

Interesting Outing 10s 1024MB