12752번 - 도시들 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 256 MB | 185 | 71 | 53 | 40.458% |
문제
사과나라에는 n 개의 도시들이 존재하며, 이 중 k 개의 도시는 국왕 구사과가 자주 방문하는 중요한 도시들이다. 또한 사과나라에는 m 개의 도시와 도시를 잇는 도로가 존재한다. 각각의 도시들은 1~n의 번호가 매겨져 있다.
어느 날 갑자기 사과나라에 폭풍이 몰아쳤다. 이 폭풍은 사과나라 건국 이래 최대 규모의 자연 재해였으며, 이때문에 모든 도로들은 제 구실을 하지 못하게 되었다. 따라서 사과나라의 대신들은 도시들 간의 교류를 이어나가기 위해 도로들을 재건하기로 결정하였다. 이를 위해, 대신들은 각각의 도로를 재건하는 데 드는 비용을 조사하여 알아내었다.
그러나, 평소 사치와 향락에 찌든 생활을 하던 구사과 때문에 사과나라의 국고는 텅텅 비어버렸고, 이때문에 모든 도로를 재건할 수는 없었다. 대신들은 일단 급한 대로 모든 중요한 도시가 서로 이어질 수 있도록 (즉, 각각의 중요한 도시들에서 다른 모든 중요한 도시에 도달할 수 있도록) 우선적으로 도로를 재건하고자 한다.
대신들은 세계 최고의 프로그래머인 당신에게 모든 중요한 도시가 서로 이어질 수 있도록 도로를 재건하는 최소 비용을 알아내도록 의뢰하였다. 우매한 사과나라 사람들에게 당신의 실력을 보여 주자.
입력
첫 번째 줄에는 도시의 개수 n, 중요한 도시의 개수 k, 도로의 개수 m이 공백으로 구분되어 주어진다.
두 번째 줄에는 공백으로 구분된 k개의 수들이 주어진다. 이 수들은 1 이상 n 이하의 서로 다른 정수들로, 중요한 도시들의 번호를 나타낸다.
다음 줄부터는 m개의 줄에 걸쳐 각 도로에 대한 정보가 주어진다. 각 줄에는 세 정수 a, b, c가 주어진다. 이는 이 도로가 도시 a와 도시 b를 잇고 있으며, 이 도로를 재건하는 데에 c의 비용이 소모된다는 뜻이다.
모든 도시들이 도로를 통해 연결되어 있다
출력
당신은 모든 중요한 도시가 서로 이어질 수 있도록 도로를 재건하는 최소 비용을 하나의 정수로 출력해야 한다.
제한
- 1 ≤ c ≤ 109
- n ≥ k
서브태스크 1 (22점)
- 2 ≤ k ≤ 5
- n ≤ 20
- 1 ≤ m ≤ 40
서브태스크 2 (14점)
- 2 ≤ k ≤ 3
- n ≤ 105
- 1 ≤ m ≤ 2 ⋅ 105
서브태스크 3 (15점)
- 2 ≤ k ≤ 4
- n ≤ 1000
- 1 ≤ m ≤ 2000
서브태스크 4 (23점)
- k = 4
- n ≤ 105
- 1 ≤ m ≤ 2 ⋅ 105
서브태스크 5 (26점)
- k = 5
- n ≤ 105
- 1 ≤ m ≤ 2 ⋅ 105
예제 입력 1
4 3 6 1 3 4 1 2 4 1 3 9 1 4 6 2 3 2 2 4 5 3 4 8
예제 출력 1
11
출처
Olympiad > Baltic Olympiad in Informatics > BOI 2016 4번
- 문제를 번역한 사람: khsoo01
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호