9694번 - 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 1749 | 641 | 491 | 38.389% |
문제
한신이는 젊고, 똑똑하고 매우 유명한 정치인이다. 그럼에도 그는 여전히 자신의 성공을 위해서도 인간관계는 중요한것이라고 믿고있다. 다음달에 열릴 국회의원선거에서 한신이는 자신의 당이 반드시 이기길 희망한다. 그러기 위해서 최고의원의 지지가 필요하다.
이 최고의원의 지지를 받기위해 한신이는 전략을 세웠다. 그는 그 최고의원을 직접적으로 만날수 없다면 그를 알고있는 인맥을 이용하여 만날것이다. 이것을 위해서 우선 정치인들의 친밀도를 조사하였는데 친밀도를 다음 4단계로 나누어서 기록해놓았다.
최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4]
[두 사람의 관계는 이 4가지 경우중 반드시 해당되며, 적(enemy)는 존재하지 않는다.]
한신이는 지인보다는 최측근 친구에게 소개받기 원한다. 그래서 최고의원을 만나기까지의 인맥간 친밀도의 합을 최소화하고 싶어한다.
N명의 정치인 명단으로부터 그들의 인맥 친밀도가 주어진다. 정치인 리스트를 보고 한신이가 최고의원을 만나기까지의 친밀도의 합 중에서 가장 작은 값을 구하면 된다.
입력
맨위 첫 번째 줄에 T(1 <T< 100)는 테스트케이스 수를 의미한다. 이것을 따라 다음줄에 각 테스트 케이스가 주어지는데, 첫 번째 줄에는 N과 M이 주어진다. N(N ≤ 20)은 관계의 개수를 의미하며, M(5 ≤M≤ 20)은 정치인의 수를 나타낸다. 이 다음 N줄에는 정치인 x, 그의 친구 y (0 ≤x,y< M), 두사람간의 친밀도 z(1 ≤z≤ 4)를 입력받는다. 정치인 0번은 한신이를 나타내고 M-1은 최고의원을 의미한다.
출력
각 테스트 케이스는 "Case #x: "의 형식으로 출력되며 x는 케이스 번호(1부터 시작)을 의미한다. 콜론뒤에 한신이가 최고의원을 만날수 있다면 0번 정치인(한신이)를 시작으로 M-1번 정치인(최고의원)까지 만난 순서대로 출력하면 되고, 최고의원을 만날수 없는 경우엔 -1을 출력하면 된다.
예제 입력 1
2 7 5 0 1 2 1 3 4 0 2 1 0 4 3 3 2 3 3 4 4 2 4 1 3 5 0 1 2 1 3 4 4 2 1
예제 출력 1
Case #1: 0 2 4 Case #2: -1
힌트
첫 번째 테스트 케이스에서 보면 한신이는 1번 정치인(한신이의 측근[2])에게 3번 정치인(1번 정치인의 지인[4])을 소개받고, 이 3번 정치인은 4번 정치인(3번 정치인의 지인[4])을 만나는 경우 2+4+4 = 10이다.
한신이가 곧바로 4번 정치인(한신이의 비즈니스관계[3])에게 얘기할수 있지만 대신에 2번 정치인(한신이의 최측근[1])에게 4번 정치인(2번 정치인의 최측근[1])을 소개 받아 만난다면 한신이는 더 좋은 인상으로 최고의원을 만날수 있을것이다.
출처
ICPC > Regionals > Asia Pacific > Malaysia > Malaysia National Programming Contest > Al-Khawarizmi National Programming Contest 2013 B번
- 문제를 번역한 사람: vumbumy
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호