| r12 ➤ r13 |
| 51 | 김도훈은 전람회 때문에 학교 도면을 찾아보다가 인곽 탈출이 가능한 비밀의 문 N곳을 찾고야 말았다. |
| 52 | |
| 53 | 각 비밀의 문은 고유번호로 구분되며 1부터 N까지 차례대로 번호가 매겨져 있었다. |
| 54 | |
| 55 | 이 N개의 비밀의 문은 서로를 연결하는 M개의 단방향 연결 통로 Pi가 존재하는데, 이동을 하려면 일정량의 에너지를 소모하여야 한다. |
| 56 | |
| 57 | 비밀의 문 Xi에서 Yi로 최적의 경로로 이동하였을 때 소모되는 에너지양을 계산하는 프로그램을 작성하시오. |
| 58 | |
| 59 | 최적의 경로란 최소한의 에너지만을 소모하는 경로를 말한다. |
| 60 | |
| 61 | |
| 62 | *입력 설명 |
| 63 | (1) 첫 번째 줄에 비밀의 문 개수 N, 이를 서로 연결하는 연결 통로의 개수 M이 공백으로 분리되어 입력된다. |
| 64 | (1 ≤ N ≤ 200, 1 ≤ M ≤ 10,000) |
| 65 | |
| 66 | |
| 67 | (2) 두 번째 줄부터 M개 줄에 걸쳐 연결 통로 정보 Pi (a, b, c)가 공백으로 분리되어 세 개의 정수로 입력된다. 이는 비밀의 문 a에서 b로의 단방향 연결 통로 이용에 c의 에너지가 소모된다는 뜻이다. |
| 68 | (1 ≤ a, b ≤ 200, 0 ≤ c ≤ 100) |
| 69 | |
| 70 | |
| 71 | (3) 그 다음 줄에는 최적의 경로 이동에 소모되는 에너지량 계산을 수행할 횟수 Z가 입력된다. |
| 72 | (1 ≤ Z ≤ 200) |
| 73 | |
| 74 | |
| 75 | (4) 그 다음부터 Z개의 줄에 걸쳐 출발지와 도착지(Xi, Yi) 정보가 공백으로 분리되어 입력된다. (1 ≤ Xi, Yi ≤ 200) |
| 76 | |
| 77 | *출력 설명 |
| 78 | 주어진 Z개의 출발지와 도착지에 대하여 최적의 경로 이동에 소모되는 에너지양을 Z개의 줄에 걸쳐 출력하시오. |
| 79 | 만약, 도달 불가능한 지점이라면 INF를 출력한다. |
| 80 | |
| 81 | *입력 예시 |
| 82 | 4 4 |
| 83 | 1 2 8 |
| 84 | 1 3 4 |
| 85 | 2 1 1 |
| 86 | 3 2 2 |
| 87 | 3 |
| 88 | 1 2 |
| 89 | 2 3 |
| 90 | 4 1 |
| 91 | |
| 92 | *출력 예시 |
| 93 | 6 |
| 94 | 5 |
| 95 | INF |
