만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

지하철 타기 (작은 입력)

시간 제한5초메모리 제한512 MB

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

보통10점 중 4점

유형
최단 경로, 그래프
정답자
아직 제출이 없습니다

문제

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

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

  • 도시에는 지하철 노선이 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분이다.

예제5

  1. 예제 1

    입력
    2

2
5 3
3 5 7 3
4 2
1 1 1
1
1 2 2 2 1
1
1 1 2 4

2
5 3
3 5 7 3
4 2
1 1 1
2
1 2 2 2 1
2 4 1 4 1
1
1 1 1 5
    예상 출력
    Case #1:
11
Case #2:
18

  2. 예제 2

    입력
    1
1
2 5
7
0
1
1 1 1 2
    예상 출력
    Case #1:
12

  3. 예제 3

    입력
    1
2
3 4
2 3
2 10
5
0
2
1 1 1 3
1 1 2 2
    예상 출력
    Case #1:
9
-1

  4. 예제 4

    입력
    1
3
2 1
10
2 1
10
2 1
10
2
1 2 2 1 2
2 2 3 1 2
1
1 1 3 2
    예상 출력
    Case #1:
37

  5. 예제 5

    입력
    1
2
5 3
3 5 7 3
4 2
1 1 1
1
1 2 2 2 1
4
1 1 2 4
2 4 1 1
1 1 1 5
2 1 2 4
    예상 출력
    Case #1:
11
11
21
5