AMR11F - Magical Bridges

no tags 

 

Hogwarts School of Witchcraft and Wizardry has a circular lane having N towers numbered 1 to N. Towers i and i+1 are adjacent to each other for 1 ≤ i < N and also towers 1 and N are adjacent to each other. Each of these towers has exactly F number of floors, numbered 1,2,3,..,F-1,F from bottom to top. Floors i and i+1 in a tower are adjacent to each other and it takes one second to move between them. It also takes one second to move between floor 1 of a tower and floor 1 of its adjacent tower. Apart from these, there are M bridges designed for a quick escape in case of a Death Eater attack, each of which connects two floors of different towers. Each of these bridges is given as bi fi bj fj t, meaning it takes t seconds to move along this bridge that connects the floor fi of tower bi and the floor fj of tower bj. All ways are bidirectional.
Given (qbi,qfi) and (qbj,qfj), find the minimum time in seconds it takes to reach floor qfj of tower qbj, starting from floor qfi of tower qbi. You have to answer a lot of such queries.
Input (STDIN):
The first line contains the number of test cases T. T cases follow. Each test case consists of N F M in the first line. N is the number of towers, F is the number of floors in each tower and M is the number of bridges. M lines follow, each of the form bi fi bj fj t, as mentioned in the problem statement. Next line contains Q, the number of queries and Q lines follow, each of the form qbi qfi qbj qfj.
Output (STDOUT):
For each query of the form qbi qfi qbj qfj, output one line denoting the minimum time in seconds it takes to reach the floor qfj of tower qbj, starting from the floor qfi of tower qbi.
Constraints:
1 ≤ T ≤ 3
2 ≤ N, M ≤ 100
2 ≤ F ≤ 1,000,000
1 ≤ t ≤ 1,000,000
1 ≤ Q ≤ 100,000
1 ≤ bi, bj, qbi, qbj ≤ N
1 ≤ fi, fj, qfi, qfj ≤ F
Time Limit : 5s
Memory Limit : 64 MB
Sample Input:
1
5 4 3
1 3 2 4 3
2 3 3 3 2
3 4 5 3 1
5
1 3 2 3
1 3 3 2
1 1 3 4
3 3 4 4
4 3 4 4
Sample Output:
4
5
4
6
1

Hogwarts School of Witchcraft and Wizardry has a circular lane having N towers numbered 1 to N. Towers i and i+1 are adjacent to each other for 1 ≤ i < N and also towers 1 and N are adjacent to each other. Each of these towers has exactly F number of floors, numbered 1,2,3,..,F-1,F from bottom to top. Floors i and i+1 in a tower are adjacent to each other and it takes one second to move between them. It also takes one second to move between floor 1 of a tower and floor 1 of its adjacent tower. Apart from these, there are M bridges designed for a quick escape in case of a Death Eater attack, each of which connects two floors of different towers. Each of these bridges is given as bi fi bj fj t, meaning it takes t seconds to move along this bridge that connects the floor fi of tower bi and the floor fj of tower bj. All ways are bidirectional.

Given (qbi,qfi) and (qbj,qfj), find the minimum time in seconds it takes to reach floor qfj of tower qbj, starting from floor qfi of tower qbi. You have to answer a lot of such queries.

 

Input (STDIN):

The first line contains the number of test cases T. T cases follow. Each test case consists of N F M in the first line. N is the number of towers, F is the number of floors in each tower and M is the number of bridges. M lines follow, each of the form bi fi bj fj t, as mentioned in the problem statement. Next line contains Q, the number of queries and Q lines follow, each of the form qbi qfi qbj qfj.

 

Output (STDOUT):

For each query of the form qbi qfi qbj qfj, output one line denoting the minimum time in seconds it takes to reach the floor qfj of tower qbj, starting from the floor qfi of tower qbi.

 

Constraints:

1 ≤ T ≤ 3

2 ≤ N, M ≤ 100

2 ≤ F ≤ 1,000,000

1 ≤ t ≤ 1,000,000

1 ≤ Q ≤ 100,000

1 ≤ bi, bj, qbi, qbj ≤ N

1 ≤ fi, fj, qfi, qfj ≤ F

 

Sample Input:

1

5 4 3

1 3 2 4 3

2 3 3 3 2

3 4 5 3 1

5

1 3 2 3

1 3 3 2

1 1 3 4

3 3 4 4

4 3 4 4

 

Sample Output:

4

5

4

6

1

 

 


hide comments
bluejam: 2017-06-16 17:32:07

AC in one go.
Wasnt expecting it after finding some silly bugs in my program

hodobox: 2016-07-16 00:42:35

Sigh, over 20 RE/WA because I put ios::sync_with_stdio(false) into solve() function instead of main, and it corrupted the input (but not on my PC of course...).
P.S. I passed with ( (N+M)^3 + Q*M)

Dhawal Harkawat: 2015-10-21 13:27:49

1.5 days, 220 lines of code, AC in one go, Awesome problem. Thanks @Varun Jalan.

Maverick: 2015-08-18 02:07:48

Awesome Awesome Awesome Problem!! Classic Problem to learn representing a graph and running Floyd Warshall.Great! Passed in Java.

THECOLDONE: 2015-06-30 12:06:29

very nice probem enjoy it

Utkarsh Agarwal: 2015-05-25 00:55:21

its simple dijisktra ?? isnt it ?

Umair Khan: 2014-09-18 07:16:17

Last edit: 2014-09-23 22:42:36
jack(chakradarraju): 2012-04-09 12:15:12

O(Q*M) is not enough?
or do i need constant optimisation?

Edit:
Great question.
O(Q*log(M)) passes in time.

Last edit: 2012-04-10 12:13:35

Added by:Varun Jalan
Date:2011-12-15
Time limit:0.692s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Anil Kishore - ICPC Asia regionals, Amritapuri 2011