cho.sh

지하철 타기 (라지)

같은 노선에 탈 때마다 대기 시간을 더하고 터널로 환승하며 두 지하철역 사이 가장 빠른 경로를 구합니다.

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

문제

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

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

  • 도시에는 지하철 노선이 NN개 있고, 1번부터 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,jS_{i,j}에서 Si,j+1S_{i,j+1}까지 가는 데 Timei,j\text{Time}_{i,j}분이 걸리며, 반대 방향도 같은 시간이 걸린다.
  • 환승 통로가 MM개 있다. 각 통로는 서로 다른 노선에 속한 두 역을 잇고, 어느 방향으로 걸어가도 같은 시간이 걸린다. 통로의 한쪽 끝 역에서 내린 다음 통로를 걸어가면 반대쪽 끝 역에 도착한다.
  • ii번 노선의 열차를 탈 때마다 그 열차를 기다리는 데 WiW_i분이 걸린다. 열차에 탄 채로 역을 지나갈 때는 시간이 더 들지 않고, 내릴 때도 시간이 들지 않는다.

한 역에서 출발해 다른 역까지 갈 때 걸리는 가장 짧은 시간을 구하라.

입력

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

각 테스트 케이스의 첫째 줄에는 노선의 수 NN이 주어진다. 이어서 노선 NN개의 정보가 주어진다. ii번 노선의 정보는 역의 수 SNiSN_i와 기다리는 시간 WiW_i가 적힌 줄로 시작한다. 다음 줄에는 이웃한 두 역 사이의 이동 시간 Timei,1,Timei,2,…,Timei,SNi−1\text{Time}_{i,1}, \text{Time}_{i,2}, \dots, \text{Time}_{i,SN_i-1}이 정수 SNi−1SN_i - 1개로 주어진다.

노선 정보 다음 줄에는 환승 통로의 수 MM이 주어지고, 이어서 MM개의 줄이 주어진다. 각 줄에는 정수 다섯 개 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개의 줄이 주어진다. 각 줄에는 정수 네 개 x1x_1, y1y_1, x2x_2, y2y_2가 주어지며, Sx1,y1S_{x_1,y_1} 역에서 Sx2,y2S_{x_2,y_2} 역까지 이동한다는 뜻이다.

제한:

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤1001 \le N \le 100
  • 2≤SNi≤10002 \le SN_i \le 1000이고, 한 테스트 케이스의 역은 모두 합쳐 1000개 이하다
  • 1≤Wi≤1001 \le W_i \le 100
  • 1≤Timei,j≤1001 \le \text{Time}_{i,j} \le 100
  • 0≤M≤1000 \le M \le 100
  • 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}, m1i≠m2im1_i \ne m2_i
  • 1≤ti≤1001 \le t_i \le 100
  • 1≤Q≤101 \le Q \le 10
  • 1≤x1≤N1 \le x_1 \le N, 1≤y1≤SNx11 \le y_1 \le SN_{x_1}, 1≤x2≤N1 \le x_2 \le N, 1≤y2≤SNx21 \le y_2 \le SN_{x_2}
  • Sx1,y1S_{x_1,y_1} 역과 Sx2,y2S_{x_2,y_2} 역은 서로 다르다

출력

각 테스트 케이스마다 Case #x:를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. 이어서 QQ개의 줄을 출력한다. kk번째 줄에는 kk번째 질의의 최소 이동 시간을 출력하고, 도착할 수 없으면 -1을 출력한다.

힌트

예제 입력의 첫 번째 테스트 케이스에 있는 질의는 1번 노선 1번 역에서 2번 노선 4번 역까지 가는 경우다. 가장 빠른 경로 하나는 다음과 같다.

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

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