Under construction

Still being built. Things may change

Taking Metro (Small)

Time limit5sMemory limit512 MB

Summary
Find the fastest route between two metro stations, combining per-line boarding waits, ride times, and tunnel walks.
Level

Medium4 of 10

Topics
Shortest path, Graph
Solved
No attempts yet

Problem

Tom rides the metro to get from one station to another.

The metro system works like this.

  • The city has NN metro lines: line 1, line 2, ..., line NN.
  • Line ii has SNiSN_i stations, listed from one terminus to the other as Si,1,Si,2,…,Si,SNiS_{i,1}, S_{i,2}, \dots, S_{i,SN_i}. Trains run in both directions, that is Si,1→Si,2→⋯→Si,SNiS_{i,1} \to S_{i,2} \to \dots \to S_{i,SN_i} and Si,SNi→Si,SNi−1→⋯→Si,1S_{i,SN_i} \to S_{i,SN_i-1} \to \dots \to S_{i,1}. You can board at any station and get off at any station. Travelling between two neighbouring stations takes time: Timei,1Time_{i,1} minutes from Si,1S_{i,1} to Si,2S_{i,2}, Timei,2Time_{i,2} minutes from Si,2S_{i,2} to Si,3S_{i,3}, and so on. The other direction takes the same time.
  • There are MM transfer tunnels. Each tunnel connects two stations of two different lines. Walking through a tunnel takes a fixed time, the same in either direction. You can get off at the station on one end of a tunnel and walk to the station on the other end.
  • To board a train at a station of line ii you have to wait WiW_i minutes. This also applies to the first train you board, at the starting station.

You are going to travel from one station to another. Find the smallest possible time.

Input

The first line contains the number of test cases, TT. TT test cases follow.

Each test case starts with a line containing the number of metro lines, NN. Descriptions of NN lines follow. Each line description starts with a row holding the number of stations SNiSN_i and the waiting time WiW_i. The next row holds SNi−1SN_i - 1 integers Timei,1,Timei,2,…,Timei,SNi−1Time_{i,1}, Time_{i,2}, \dots, Time_{i,SN_i-1}, the travel times between neighbouring stations.

After the line descriptions comes a row holding the number of tunnels, MM. Each of the next MM rows holds 5 integers m1im1_i, s1is1_i, m2im2_i, s2is2_i, tit_i: the tunnel connects station Sm1i,s1iS_{m1_i,s1_i} and station Sm2i,s2iS_{m2_i,s2_i}, and walking through it takes tit_i minutes.

The next row holds the number of queries, QQ. Each of the next QQ rows holds 4 integers x1x1, y1y1, x2x2, y2y2, meaning you travel from station Sx1,y1S_{x1,y1} to station Sx2,y2S_{x2,y2}.

Limits

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤101 \le N \le 10
  • 2≤SNi≤1002 \le SN_i \le 100
  • The total number of stations in one test case is at most 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 and m2im2_i are different.
  • 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}
  • Station Sx1,y1S_{x1,y1} and station Sx2,y2S_{x2,y2} are different.

Output

For each test case, first print Case #x:, where x is the test case number starting from 1. Then print QQ lines, one per query in the order given. Each line holds the smallest time for that query as an integer, or -1 if the trip is impossible.

Note

In the first test case of the first example you travel from station 1 of line 1 to station 4 of line 2. The fastest way is:

  • wait 3 minutes for a train on line 1 and board it,
  • ride for 3 minutes and get off at station 2,
  • walk through the tunnel for 1 minute to station 2 of line 2,
  • wait 2 minutes for a train on line 2 and board it,
  • ride for 2 minutes and get off at station 4.

The time spent is 3+3+1+2+2=113+3+1+2+2=11 minutes.

Examples5

  1. Example 1

    Input
    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
    Expected output
    Case #1:
11
Case #2:
18

  2. Example 2

    Input
    1
1
2 5
7
0
1
1 1 1 2
    Expected output
    Case #1:
12

  3. Example 3

    Input
    1
2
3 4
2 3
2 10
5
0
2
1 1 1 3
1 1 2 2
    Expected output
    Case #1:
9
-1

  4. Example 4

    Input
    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
    Expected output
    Case #1:
37

  5. Example 5

    Input
    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
    Expected output
    Case #1:
11
11
21
5