|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|5 초||512 MB||8||6||6||75.000%|
Tom is taking metros in the city to go from station to station.
The metro system in the city works like this:
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 SNi and Wi, the number of stations and the expected waiting time in minutes. The next line consists of SNi-1 integers, Timei,1, Timei,2, ..., Timei,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, m1i, s1i, m2i, s2i, ti which means the tunnel is connecting stations Sm1i,s1i and station Sm2i,s2i. The walking time of the tunnel is ti.
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 Sx1,y1 to station Sx2,y2.
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.
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
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:
The total time is: 3+3+1+2+2=11.