12193번 - Taking Metro (Large) 다국어

Tom is taking metros in the city to go from station to station.

The metro system in the city works like this:

• There are N metro lines in the city: line 1, line 2, ..., line N.
• For each metro i, there are SN_i stations. Let's assume they are S_i,1,S_i,2, ... , S_i,SNi. These stations are ordered from one end point to the other end point. The metro is running in both directions. In other words, the metro is going from S_i,1 -> S_i,2 -> ... -> S_i,SNi, and S_i,SNi -> S_i,SNi-1 -> ... -> S_i,1. You can take the metro from any station and get off at any station. It takes a certain time to travel from one station to the next station. It takes Time_i,1 minutes to travel from S_i,1 to S_i,2, Time_i,2 minutes to travel from S_i,2 to S_i,3, etc. It takes the same time in the other direction.
• There are M transfer tunnels. Each transfer tunnel connects two stations of different metro lines. It takes a certain amount of time to travel through a tunnel in either direction. You can get off the metro at one end of the tunnel and walk through the tunnel to the station at the another end.
• When you arrive at a metro station of line i, you need to wait W_i minutes for the next metro.

Now, you are going to travel from one station to another. Find out the shortest time you need.

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case starts with an integer N, the number of metro lines. N metros descriptions follow. Each metro description starts with two integers SN_i and W_i, the number of stations and the expected waiting time in minutes. The next line consists of SN_i-1 integers, Time_i,1, Time_i,2, ..., Time_i,SNi-1, describing the travel time between stations.

After the metro descriptions, there is an integer M, the number of tunnels. M lines follow to describe the tunnels. Each tunnel description consists of 5 integers, m1_i, s1_i, m2_i, s2_i, t_i which means the tunnel is connecting stations S_m1i,s1i and station S_m2i,s2i. The walking time of the tunnel is t_i.

The next line contains an integer Q, the number of queries. Each of the next Q lines consists of 4 integers, x1, y1, x2, y2, which mean you are going to travel from station S_x1,y1 to station S_x2,y2.

Limits

• 1 ≤ T ≤ 100.
• 1 ≤ W_i ≤ 100.
• 1 ≤ Time_i,j ≤ 100.
• 1 ≤ m1_i ≤ N.
• 1 ≤ s1_i ≤ SN_m1i.
• 1 ≤ m2_i ≤ N.
• 1 ≤ s2_i ≤ SN_m2i.
• m1_i and m2_i will be different.
• 1 ≤ t_i ≤ 100.
• 1 ≤ Q ≤ 10.
• 1 ≤ x1 ≤ N.
• 1 ≤ y1 ≤ SN_x1.
• 1 ≤ x2 ≤ N.
• 1 ≤ y2 ≤ SN_y2.
• Station S_x1,y1 and station S_x2,y2 will be different.
• 1 ≤ N ≤ 100.
• 0 ≤ M ≤ 100.
• 2 ≤ SN_i ≤ 1000.
• The total number of stations in each case is at most 1000.

For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1), then followed by Q lines, each line containing an integer y which is the shortest time you need for that query. If it's impossible, output -1 for that query instead.

In the first case, you are going to travel from station 1 of metro line 1 to station 4 of metro line 2. The best way is:

• wait 3 minutes for line 1 and get on it.
• take it for 3 minutes and get off at station 2.
• take the tunnel and walk for 1 minute to station 2 of line 2.
• wait 2 minutes for line 2 and get on it.
• take it for 2 minutes and get off at station 4.

The total time is: 3+3+1+2+2=11.