COCI 2014/2015 contest1 6- 본부를 어디에 세울까?(KAMP) > 문제은행 : 정보올림피아드&알고리즘




2871 : 본부를 어디에 세울까?(KAMP)

제한시간
2000 ms   
메모리제한
128 MB   
해결횟수
9 회   
시도횟수
25 회   

문제

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

 

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

 

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

 

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


입력형식

첫 행에 집 수 N( 1 ≤ N ≤ 500,000)과 물에 잠긴 집의 수 K( 1 ≤ K ≤N)이 입력된다.

이 후 N-1개의 행에 Ai, Bi, Ci ( 1 ≤ Ai, Bi, ≤ N, 1 ≤ Ci ≤ 1,000,000)가 입력되는데 Ci는 Ai, Bi두 집 사이의 이동 시간을 나타낸다. 

이 후 K개의 행에 피해를 입은 집의 번호 Hi ( 1≤ Hi ≤ N)가 입력된다.


출력형식

N개의 행에 걸쳐 i번째는 i번 집을 본부로 할 때 모든 피해 현장에 봉사대를 수송하는 최소 시간을 출력한다.


<입력 예1 에 대한 설명> 

한 예를 들면 아래와 같다. 

 

1번 집을 본부로 하면 1-2-4-2-5의 경로로 이동하므로 이동 시간의 합은 5이다. 

2번 집을 본부로 하면 2-4-2-5의 경로로 이동하므로 이동 시간의 합은 3이다. 

3번 집을 본부로 하면 3-1-2-4-2-5의 경로로 이동하므로 이동 시간의 합은 7이다.

4번 집을 본부로 하면 4-2-5의 경로로 이동하므로 이동 시간의 합은 2이다. 

5번 집을 본부로 하면 5-2-4의 경로로 이동하므로 이동 시간의 합은 2이다.


입력 예

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

출력 예

5
3
7
2
2

입력 예

7 2
1 2 4
1 3 1
2 5 1
2 4 2
4 7 3
4 6 2
3
7

출력 예

11
15
10
13
16
15
10


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP