Commuting Mathematicians

지하철을 타고 이동하는 동안 최신 과학, 기술, 공학, 수학의 발전을 논하는 것은 ACM(Commuting Mathematicians 협회)의 오랜 전통이다. 지하철 여행 중에 ACM 회원들은 협회의 첫 번째 기본 규칙인 "걸으면서 말하지 말 것"을 철저히 지킨다. 따라서 다른 지하철 노선으로 갈아타야 하는 구간에서 논의는 중단된다. ACM 회원들은 또한 건망증이 심한 교수라는 고정관념에 딱 들어맞아서, 환승할 때 항상 현재 주제를 잊고 새 노선의 좌석에 앉으면 전혀 상관없는 새 논의를 시작한다. 그래서 논의는 좀처럼 결론에 도달하지 못한다.

ACM 회원들은 지하철에서 이 문제를 논의한 끝에, 이동 시간과 환승 횟수를 모두 최소화하면서 지하철로 도시를 빠르고 간단하게 돌아다닐 방법이 필요하다는 데 합의했다. 그들은 이 과제의 최적해를 찾기 직전이었지만, 안타깝게도 환승을 해야 했고 대신 무선 네트워크와 마못에 대한 이야기를 시작했다... 따라서 이 성가신 문제를 해결하는 것은 여러분의 몫이다.

지하철 네트워크는 역과 지하철 노선으로 이루어진 그래프다. 역은 음이 아닌 정수로 식별된다. 예를 들어 42와 같다. 지하철 노선은 정차역의 나열이며, 각 정차역은 역이고 인접한 두 역 사이에는 이동 시간이 있다. 예를 들어 Figure 4의 예제 1에는 파란색 노선, 초록색 노선, 주황색 노선의 세 노선이 있다. 지하철 차량은 노선을 양방향으로 따른다. 어느 방향이든 이동 시간은 같고, 한 노선에서 다른 노선으로 환승할 때의 대기 시간은 무시한다. 노선의 정차역은 항상 서로 다른 역에 대응하지만, 노선이 순환할 수 있다. 이 경우 마지막 정차역은 첫 번째 정차역과 같은 역이며, 지하철 차량은 노선을 양방향으로 따른다.

지하철 네트워크의 세부 정보를 알고, 출발역에서 도착역까지 ACM 회원들을 위한 최적의 이동 경로를 찾아야 한다. 알고리즘의 첫 번째 목표는 이동 시간을 최소화하는 것이다. 또한 최소 이동 시간을 갖는 모든 경로 중에서 알고리즘은 한 노선에서 다른 노선으로의 환승 횟수도 최소화해야 한다. 한 노선에서 그 노선 자체로 환승하는 것은 결코 가능하지도 유용하지도 않다.

입력은 여러 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 수를 나타내는 정수가 주어진다. 각 테스트 케이스가 이어진다. 테스트 케이스의 첫 줄은 공백 하나로 구분된 두 양의 정수 0 < N ≤ 1000과 0 < L ≤ 50으로 이루어진다. N은 역의 수, L은 지하철 노선의 수다. 이어서 L개의 줄이 각 지하철 노선을 설명하며, 각 줄은 공백 하나로 구분된 다음 정수들로 이루어진다. 첫 정수 1 < Ki ≤ N + 1은 노선의 정차역 수이고, 다음 2 · Ki − 1개의 정수 Si,1, Ti,1↔2, Si,2, Ti,2↔3, . . . , Si,Ki−1, Ti,(Ki−1)↔Ki, Si,Ki는 정차역과 정차역 사이의 이동 시간을 나타낸다. 구체적으로, 1 ≤ j ≤ Ki에 대해 정수 0 ≤ Si,j < N은 i번째 노선의 j번째 정차역의 역을 나타내고, 1 ≤ j < Ki에 대해 정수 0 < Ti,j↔(j+1) ≤ 60은 이 노선의 j번째 정차역과 j + 1번째 정차역 사이의 이동 시간을 분 단위로 나타낸다. 순환 노선은 하나의 순환만 이룰 수 있다. 즉, 한 노선의 첫 번째 역이 그 노선의 마지막 역이기도 하다. 양 끝이 아닌 모든 정차역은 서로 달라야 한다. 즉, 1 ≤ p < q ≤ Ki인 임의의 p, q에 대해 Sp ≠ Sq이며, p = 1이고 q = Ki인 경우는 예외일 수 있다. 테스트 케이스는 공백 하나로 구분된 두 정수 0 ≤ F < N과 0 ≤ D < N으로 이루어진 줄로 끝난다. F는 출발역, D는 도착역을 나타낸다. 항상 F ≠ D이며, 역 F와 D 사이에 경로가 존재함이 보장된다.

입력의 각 테스트 케이스에 대해 공백 하나로 구분된 두 정수로 이루어진 한 줄을 출력해야 한다. 첫 번째 정수는 출발역에서 도착역까지 가는 경로의 최소 분 수여야 한다. 두 번째 정수는 최소 분 수로 출발역에서 도착역까지 가는 경로의 최소 환승 횟수여야 한다. 출력에 빈 줄이 있어서는 안 된다.

아래 예제 입력은 두 테스트 케이스를 지정한다. 각 테스트 케이스의 지하철 네트워크는 Figure 4에 나와 있다. 첫 번째 예제는 세 지하철 노선으로 이루어진다. 초록색 노선은 역 0, 1, 2에 정차하며 이동 시간은 각각 3분, 2분이다. 주황색 노선은 2와 3을 연결하고 이동 시간은 4분이다. 파란색 노선은 2와 4를 연결하고 이동 시간은 1분이다. ACM 회원들은 역 0에서 역 4로 가고 싶어 한다. 가능한 최적 경로는 6분이 걸리고 초록색 노선에서 파란색 노선으로 한 번 갈아타야 한다.

두 번째 예제는 두 노선으로 이루어진다. 초록색 노선은 네트워크의 모든 역을 연결하는 원을 이루며, 연속한 두 역 사이를 가는 데 2분이 걸린다. 주황색 노선은 역 1과 4를 직접 연결하며 이동 시간은 4분이다. 수학자들은 역 1에서 4로 가고 싶어 한다. 각각 이동 시간이 4분인 두 가지 최단 경로가 있다. 초록색 노선으로 가거나 주황색 노선으로 가는 것이다. 또한 이 두 가지 선택 모두 노선을 갈아타지 않아도 된다.

Figure 4: 예제 입력의 지하철 네트워크