29203번 - 테마파크 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 280 | 49 | 38 | 21.229% |
문제
민찬이는 테마파크를 개장했다. 이 테마파크는 각기 다른 테마들로 구성된 $N$개의 구역과 서로 다른 두 구역을 양방향으로 잇는 $N-1$개의 길로 이루어져 있다. $i$번 길은 $A_i$번 구역과 $B_i$번 구역을 양방향으로 이으며, 임의의 구역에서 다른 구역으로 가는 경로가 항상 존재한다.
이 테마파크의 구역 $N$개 중 $M$개는 유료로 운영된다. 유료로 운영되는 구역을 거쳐 가거나 그 구역에 입장하려면 티켓 하나를 사용해야 하며, 한번 사용한 티켓을 다시 사용할 수는 없다. 단, $1$번 구역은 항상 무료로 운영된다.
민찬이는 개장을 기념해서 KSA 학생을 한 구역당 한 명씩 총 $N$명 초대할 계획이다. 이때, $i$번 구역에 초대된 학생은 입구가 있는 $1$번 구역부터 $i$번 구역까지 길을 가장 적게 지나는 경로를 따라 걸어갈 것이다.
또, KSA 학생들이 돈을 내야 하는 상황을 막기 위해 민찬이는 $1$개 이상의 길 중간에 무료 티켓 행사를 열어 그 길을 지나는 학생들에게 티켓을 하나씩 무료로 나눠주려고 한다. 이때, $i$번 길에 행사를 열기 위해서는 비용이 $C_i$만큼 들고, 통행을 원활하게 하기 위해 하나의 길에는 최대 하나의 행사만 열어야 한다. KSA 학생이 모두 자신이 초대된 구역까지 무료로 갈 수 있도록 행사를 여는 최소 비용과 그 방법을 구해보자.
입력
첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다.
두 번째 줄에 유료로 운영되는 구역의 번호를 나타내는 $M$개의 정수 $X_1, X_2, \cdots, X_M$이 공백으로 구분되어 주어진다.
$i+2$번째 줄에 세 정수 $A_i$, $B_i$, $C_i$가 공백으로 구분되어 주어진다. $(1 \le i \le N-1)$
출력
첫 번째 줄에 모든 KSA 학생들이 자신이 초대된 구역까지 무료로 갈 수 있도록 행사를 여는 최소 비용을 출력한다.
두 번째 줄에 행사를 열 길의 개수 $K$를 출력한다. $(1 \leq K \leq N-1)$
세 번째 줄에 행사를 열 길의 번호를 나타내는 정수 $Y_1, Y_2, \cdots, Y_K$를 공백으로 구분하여 출력한다. $(1 \leq Y_i \leq N-1)$
정답이 여러 개 존재한다면 그중 아무거나 출력해도 상관없다.
제한
- $1 \leq M < N \leq 2 \times 10^5$
- $2 \leq X_1 < X_2 < \cdots < X_M \leq N$
- $1 \leq A_i < B_i \leq N$ $(1 \leq i \leq N-1)$
- $0 \leq C_i \leq 10^9$ $(1 \leq i \le N-1)$
- $1 \leq i < j \leq N$인 모든 $i$, $j$에 대해서 $i$번 구역과 $j$번 구역을 연결하는 경로가 존재
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | $C_i=0$ $(1 \le i \leq N-1)$ |
| 2 | 12 | $C_i=1$ $(1 \le i \leq N-1)$ |
| 3 | 47 | $N \leq 5000$ |
| 4 | 37 | 추가 제약 조건 없음 |
예제 입력 1
4 2 3 4 1 2 4 2 3 2 2 4 3
예제 출력 1
4 1 1
예제 입력 2
5 3 2 4 5 1 2 10 2 3 1 3 4 2 4 5 7
예제 출력 2
13 3 1 2 3
출처
School > 한국과학영재학교 > 2023 KSA Automata Summer Contest H번
- 문제를 만든 사람: mickeyjung
- 문제를 검수한 사람: cologne, dohoon, eric00513, flakepowders, jjkmk1013, jk410, leo020630, parkky, utilforever, yongwhan
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호