| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 23 | 11 | 10 | 45.455% |
Albert는 방학 동안 $N$ 개의 도시를 방문할 계획이다 (편의상 도시는 1번부터 $N$번까지 번호가 붙어있다). $N$ 개의 도시들은 기차, 비행기, 유람선, 버스 등 다양한 교통 수단으로 서로 연결되어 있는데, 마침 공교롭게도 $N$ 개의 다른 교통수단이 존재한다 (교통 수단도 편의상 1번부터 $N$번까지 번호가 붙어있다). 구체적으로, $D_{k, i, j}$ 는 도시 $i$ 에서 도시 $j$로 이동할 때 $k$ 번째 교통수단을 사용할 때 걸리는 시간을 나타낸다 - 단, 이 값이 0인 경우 해당 교통수단을 이용해서 $i$ 에서 $j$ 로 이동할 수 없음을 나타낸다. 또한, 이 문제에서는 항상 $D_{k, i, j} = D_{k, j, i}$ 이라 가정한다.
예를 들어, $N = 3$ 이고 $D_{1, \cdot, \cdot} = [[0, 1, 3], [1, 0, 4], [3, 4, 0]]$, $D_{2, \cdot, \cdot} = [[0, 2, 2], [2, 0, 4], [2, 4, 0]]$, $D_{3, \cdot, \cdot} = [[0, 3, 8], [3, 0, 4], [8, 4, 0]]$ 이라 하자.
다양한 교통수단과 일정을 알아보던 중, Albert는 1번 도시에서 출발하여 각 교통수단을 정확히 한 번씩 이용하고 각 도시를 정확히 한 번씩 방문한 후 다시 1번 도시로 돌아오는 방법 중 가장 시간이 적게 걸리는 경우와 가장 오래 걸리는 경우를 알고 싶어졌다.
위 예제에서 도시 1 -> 도시 2 -> 도시 3 -> 도시 1로 이동하는 방법을 생각해보자.
위 예제의 경우 Albert가 원하는 답은 7과 14가 된다. 입력으로 정수 $N$ 과 3차원 배열 $D$가 주어졌을 때, 위 조건을 만족하면서 관광할 때 걸리는 최소/최대 시간을 구해보자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N$ 이 주어진다. 다음 $N^2$ 줄에 걸쳐 각 줄에 $N$ 개의 정수가 공백으로 구분되어 주어지는데, 처음 $N$ 개의 줄은 1번째 교통 수단을 이용했을 때 도시 $i$ 에서 도시 $j$ 로 이동하는데 걸리는 시간인 $D_{1, \cdot, \cdot}$ 을 나타내고 (해당 $N$ 개의 줄 중 첫 번째 줄은 $i = 1$ 인 경우, 다음 줄은 $i = 2$ 인 경우 등을 나타낸다), 다음 $N$ 개의 줄은 2번째 교통 수단을 이용한 경우를 나타내고, 마찬가지로 $N$ 번째 교통 수단을 이용했을 때 걸리는 시간까지 순서대로 주어진다.
각 테스트 케이스의 정답인 최소 시간과 최대 시간을 공백으로 구분하여 각 줄에 출력한다. 단, 조건을 만족하면서 관광할 방법이 없는 경우 "0 0"을 출력한다 (따옴표 제외).
4 2 0 9 9 0 0 3 3 0 2 0 0 0 0 0 1 1 0 3 0 1 3 1 0 4 3 4 0 0 2 2 2 0 4 2 4 0 0 3 8 3 0 4 8 4 0 4 0 1 2 3 1 0 4 5 2 4 0 6 3 5 6 0 0 2 3 5 2 0 7 11 3 7 0 13 5 11 13 0 0 1 3 3 1 0 7 0 3 7 0 0 3 0 0 0 0 0 3 5 0 0 7 9 3 7 0 1 5 9 1 0
12 12 0 0 7 14 10 26
예제 1: 도시1 -> 도시2 -> 도시1 로 이동하는 경우 교통 수단을 1번을 먼저 이용하건 2번을 먼저 이용하건 걸리는 시간은 총 12 단위 시간으로 동일하다.
예제 2: 1번 교통수단을 이용하여 이동할 수 없으므로 조건을 만족하는 도시 관광 방법이 없다. 따라서 0 0 을 출력한다.
에제 3: 본문에서 다루었다.
예제 4: 추가 설명 없음.