소방차
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- FIRETRUCKS
- 2000ms
- 65536kb
- 2308
- 955 (41%)
-
- 출처
- 분류
문제
한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 위해 가능한 한 빠르게 소방차를 파견해야 합니다. 서울 시내에는 m개의 소방서가 있습니다. 화재 장소에서 가장 가까운 소방서에서 소방차를 보낸다고 할 때, 각 화재 장소에 소방차가 도달하기까지 걸리는 시간의 합을 계산하는 프로그램을 작성하세요. 각 소방서에는 소방차가 충분히 많습니다.
이 문제에서 서울 시내는 1부터 V까지 번호 붙여진 V개의 장소들과 이들을 연결하는 E개의 양방향 도로로 구성됩니다. 모든 도로에 대해 도로가 연결하는 두 장소의 번호와 각 도로별 통행 소요 시간이 주어집니다.
예제 지도를 봅시다. 사각형으로 표시된 지점들은 소방서를, 음영으로 칠해진 지점들은 불이 난 지점을 나타냅니다. 2번과 5번 장소에서는 6번 소방서가 가장 가깝고, 3번 장소에서는 4번 소방서가 가장 가깝습니다. 이때, 각 장소에 소방차가 도착하기까지 걸리는 시간은 2번 장소에 8분, 5번 장소에 4분, 3번 장소에 4분으로 총 합은 16분이 됩니다.
입력
입력의 첫 번째 줄에는 테스트 케이스의 수 C(1≤C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 장소의 수 V(2≤V≤1000)와 도로의 수 E(0≤E≤V*(V-1)/2) 그리고 화재 장소의 수 n과 소방서의 수 m(1≤n, 1≤m, n+m≤V)이 주어집니다. 그 후 e 줄에 각 세 개의 정수로 각 도로가 잇는 두 장소 a, b의 번호와(1≤a, b≤V) 이 도로를 통행하는 데 걸리는 시간 t가 분 단위로 주어집니다.(1≤t≤100) 테스트 케이스의 마지막 두 줄에는 각각 n개와 m개의 정수로, 화재가 발생한 장소의 번호와 소방서의 위치 번호가 주어집니다.
소방서가 있는 곳에서는 화재가 발생하지 않으며, 소방차가 도착할 수 없는 화재 장소는 없다고 가정해도 좋습니다. 입력에서 같은 장소 사이에 두 개 이상의 도로가 존재하는 일은 없으며, 모든 도로는 양방향 통행이 가능합니다.
출력
각 테스트 케이스마다 한 줄로, 각 화재 장소에 소방차가 도착하기까지 걸리는 시간의 합을 분 단위로 출력합니다.
예제 입력
1 8 12 3 2 1 2 3 1 6 9 2 3 6 3 4 4 3 5 2 4 5 7 6 5 5 8 6 5 6 7 3 8 7 3 7 5 1 2 8 3 2 3 5 4 6
예제 출력
16
노트