cho.sh

지하철 타기 (작은 입력)

노선별 승차 대기 시간과 터널 도보 시간을 더해 출발역에서 도착역까지 가장 빠른 이동 시간을 구합니다.

보통4최단 경로그래프아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

톰은 도시의 지하철을 타고 역에서 역으로 이동한다.

이 도시의 지하철은 다음과 같이 운행한다.

  • 도시에는 지하철 노선이 NN개 있다. 노선 1, 노선 2, ..., 노선 NN이다.
  • 노선 ii에는 역이 SNiSN_i개 있고, 한쪽 종점에서 반대쪽 종점까지 차례대로 Si,1,Si,2,…,Si,SNiS_{i,1}, S_{i,2}, \dots, S_{i,SN_i}이다. 열차는 양방향으로 다닌다. 즉 Si,1→Si,2→⋯→Si,SNiS_{i,1} \to S_{i,2} \to \dots \to S_{i,SN_i} 방향과 Si,SNi→Si,SNi−1→⋯→Si,1S_{i,SN_i} \to S_{i,SN_i-1} \to \dots \to S_{i,1} 방향이 모두 있다. 어느 역에서나 열차를 타고 어느 역에서나 내릴 수 있다. 이웃한 두 역 사이를 이동하는 데는 시간이 걸린다. Si,1S_{i,1}에서 Si,2S_{i,2}까지 Timei,1Time_{i,1}분, Si,2S_{i,2}에서 Si,3S_{i,3}까지 Timei,2Time_{i,2}분이 걸리고 나머지도 같은 방식이다. 반대 방향으로 이동할 때도 시간은 같다.
  • 환승 통로가 MM개 있다. 통로 하나는 서로 다른 두 노선의 역을 잇는다. 통로를 걸어서 지나는 데는 정해진 시간이 걸리며, 어느 방향으로 지나도 시간은 같다. 통로 한쪽 끝의 역에서 내린 다음 통로를 걸어 반대쪽 끝의 역으로 갈 수 있다.
  • 노선 ii의 역에서 열차를 타려면 WiW_i분을 기다려야 한다. 출발역에서 처음 열차를 탈 때도 마찬가지다.

이제 한 역에서 다른 역까지 이동하려고 한다. 걸리는 시간의 최솟값을 구하라.

입력

첫 줄에 테스트 케이스의 개수 TT가 주어진다. 이어서 테스트 케이스가 TT개 주어진다.

각 테스트 케이스는 노선의 개수 NN이 적힌 줄로 시작한다. 이어서 노선 NN개의 정보가 주어진다. 노선 하나의 정보는 역의 개수 SNiSN_i와 대기 시간 WiW_i가 적힌 줄로 시작한다. 다음 줄에는 정수 SNi−1SN_i - 1개 Timei,1,Timei,2,…,Timei,SNi−1Time_{i,1}, Time_{i,2}, \dots, Time_{i,SN_i-1}이 주어지며, 이웃한 두 역 사이의 이동 시간이다.

노선 정보 다음 줄에는 환승 통로의 개수 MM이 주어진다. 이어지는 MM개의 줄에는 정수 5개 m1im1_i, s1is1_i, m2im2_i, s2is2_i, tit_i가 주어진다. 이 통로는 역 Sm1i,s1iS_{m1_i,s1_i}과 역 Sm2i,s2iS_{m2_i,s2_i}를 잇고, 걸어서 지나는 데 tit_i분이 걸린다.

다음 줄에는 질의의 개수 QQ가 주어진다. 이어지는 QQ개의 줄에는 정수 4개 x1x1, y1y1, x2x2, y2y2가 주어지며, 역 Sx1,y1S_{x1,y1}에서 역 Sx2,y2S_{x2,y2}까지 이동한다는 뜻이다.

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤101 \le N \le 10
  • 2≤SNi≤1002 \le SN_i \le 100
  • 한 테스트 케이스에 있는 역의 총 개수는 100 이하이다.
  • 1≤Wi≤1001 \le W_i \le 100
  • 1≤Timei,j≤1001 \le Time_{i,j} \le 100
  • 0≤M≤100 \le M \le 10
  • 1≤m1i≤N1 \le m1_i \le N, 1≤s1i≤SNm1i1 \le s1_i \le SN_{m1_i}
  • 1≤m2i≤N1 \le m2_i \le N, 1≤s2i≤SNm2i1 \le s2_i \le SN_{m2_i}
  • m1im1_i와 m2im2_i는 서로 다르다.
  • 1≤ti≤1001 \le t_i \le 100
  • 1≤Q≤101 \le Q \le 10
  • 1≤x1≤N1 \le x1 \le N, 1≤y1≤SNx11 \le y1 \le SN_{x1}
  • 1≤x2≤N1 \le x2 \le N, 1≤y2≤SNx21 \le y2 \le SN_{x2}
  • 역 Sx1,y1S_{x1,y1}과 역 Sx2,y2S_{x2,y2}는 서로 다르다.

출력

각 테스트 케이스마다 먼저 Case #x:를 출력한다. 여기서 x는 테스트 케이스 번호이고 1부터 시작한다. 그 다음 QQ개의 줄에 질의의 답을 순서대로 한 줄에 하나씩 출력한다. 각 줄에는 그 질의에서 걸리는 시간의 최솟값을 정수로 출력하고, 이동할 수 없으면 -1을 출력한다.

힌트

첫 번째 예제의 첫 테스트 케이스에서는 노선 1의 1번 역에서 노선 2의 4번 역까지 간다. 가장 빠른 방법은 다음과 같다.

  • 노선 1의 열차를 3분 기다렸다가 탄다.
  • 3분 동안 타고 2번 역에서 내린다.
  • 환승 통로를 1분 동안 걸어 노선 2의 2번 역으로 간다.
  • 노선 2의 열차를 2분 기다렸다가 탄다.
  • 2분 동안 타고 4번 역에서 내린다.

걸린 시간은 3+3+1+2+2=113+3+1+2+2=11분이다.