바이트 마을에 홍수가 나서 K개의 집이 물에 잠겼다. 이 마을은 N개의 집으로 구성되어 있으며 각 집은 모두 넓은 정원을 가지고 있고 각 집의 호수는 1 ~ N까지라고 한다. 또한 N-1개의 도로가 집과 집들을 서로 연결하는데 임의의 어느 두 집의 경로는 유일하다고 한다.

물이 빠진 후 피해 복구를 위하여 마을의 이장인 효건이는 자원 봉사대를 조직하고, N개의 집 정원 중에 한 곳을 봉사대 본부로 정하기로 하였다. 대부분의 교통수단이 홍수로 사용할 수가 없게 되어 킹왕짱 버스가 한 번에 모두를 싣고 피해 현장에 차례로 내려주기로 하였다. 킹왕짱버스는 인원이나 짐이 아무리 많아도 모두 실을 수 있다고 한다.

피해지역은 여러 날을 두고 지속적으로 복구가 이루어져야 하므로 자원 봉사대 본부와 피해지역간의 거리가 가능한 짧아야 한다. 따라서 각 집을 본부로 가정하고 모든 피해 현장에 봉사대를 수송하는 최소 시간이 얼마가 되는지 알아볼 필요가 있다. 이 시간을 계산하는데 본부로 돌아오는 시간은 계산할 필요가 없다.

이 시간들을 구하기 위하여 효건이가 여러분에게 도움을 청하고 있다.

#2871 upload 35 done 15 how_to_reg 13

본부를 어디에 세울까?(KAMP) timer 2s memory 128MB

#2871

본부를 어디에 세울까?(KAMP) 2s 128MB