11808번 - 마리오와 사악한 키노피오 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 256 MB | 453 | 96 | 68 | 20.732% |
문제
마리오는 사악한 쿠파로부터 피치 공주를 구하기 위해 동분서주한다. 그러나 어떤 스테이지를 클리어하더라도, 어떤 작은 버섯 인간(키노피오)이 공주는 다른 성에 있다고 말할 뿐이었다. 마리오는 이 키노피오가 굉장히 사악한 존재이고, 단지 재미를 위해 마리오를 최대한 먼 성으로 보내려는 것이 틀림없다고 의심한다.
마리오의 세계는 N개의 노드를 가진 트리(N-1개의 간선이 존재하며, 연결 그래프이고, 각 노드는 1부터 N까지의 번호를 가짐)의 형태이다.(어째서?) 각 노드에는 성이 하나씩 존재하며, 각 간선은 하나의 스테이지를 의미한다. 마리오는 트리의 루트 노드에서 여행을 시작하여, 트리 위에서 이동하며(같은 정점이나 간선을 여러 번 지날 수 있다) 만나는 성마다 키노피오의 지시에 따라 피치 공주를 찾아 헤맨다. 스테이지 하나를 진행할 때는 일정한 시간이 소요된다(이 시간은 양쪽 방향에서 동일하다).
키노피오는 K개의 서로 다른 성을 택하며(루트 노드는 선택하지 않는다), 마리오는 이 성들을 반드시 주어진 순서에 따라 방문해야만 한다. 마리오는 반드시 여행을 루트 노드에서 시작하여, 루트 노드에서 끝내야 한다. 마리오는 항상 성으로 이동할 때마다 최단 경로를 통해서만 움직인다. 키노피오가 K개의 성을 뽑는 경우에 따라 마리오가 여행을 하는 데 걸리는 최장 시간은 얼마인가?
입력
첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 100)
각 테스트 케이스의 첫 번째 줄에는 2개의 정수 N, K가 주어지며, (2 ≤ N ≤ 1,000) (1 ≤ K ≤ 100) (1 ≤ K ≤ N - 1) N은 성의 개수이고 K는 키노피오가 선택할 성의 개수이다.
다음 N-1개의 줄에 걸쳐서 2~N번 노드의 정보가 순서대로 주어진다. 각 줄마다 2개의 정수 Pi, Ci가 주어지며, (1 ≤ Pi ≤ N ) (0 ≤ Ci ≤ 100,000) 각각 해당 노드의 부모 노드 번호와, 부모와 자신 사이의 스테이지를 지나는 데 소요되는 시간을 의미한다.
항상 루트 노드는 1번 노드이다.
출력
각 테스트 케이스마다 한 줄에 걸쳐 “Case n:”의 양식과 함께 답을 출력한다. n은 테스트 케이스의 번호를 의미하며, 1부터 시작한다.
예제 입력 1
3 3 1 1 5 1 3 4 2 1 5 1 3 3 2 5 3 1 5 1 3 3 2 3 10
예제 출력 1
Case 1: 10 Case 2: 20 Case 3: 46
힌트
세 번째 테스트 케이스의 경우, 키노피오가 5, 2, 4번 성을 순서대로 뽑으면 가능하다. 4, 2, 5번도 가능하다.
출처
ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2014 Arab Collegiate Programming Contest J번
- 문제를 번역한 사람: kks227
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호