Shortest Distance

Moderate

0/80

Average time to solve is 15m

Contributed by

1 upvote

Asked in companies

Problem statement

Ninjaland is a country consisting of ‘N’ states and ‘M’ paths. There are two types of paths that connect any two states. One is the normal path, and the other is a special path. Both paths have their respective lengths. You can use either of the paths to travel between two states. Your task is to determine the shortest distance between the two given states such that at most, one(possibly zero) special path is included in this path.

Note:

1. All the paths are directed.

2. Multiple paths can be present between two states.

3. All the states are connected with each other.

4. It does not have any self-loop.

5. At least one path always exists between the two given states.

For Example:

If ‘N’ = 3, ‘M’ = 2, and given values of paths are 
[ [1, 2, 2, 3],
  [2, 3, 4, 2] ]
You have to calculate the shortest distance between ‘X’ = 1 and ‘Y’ = 3

In the diagram, we can observe no direct edge from state 1 to state, 3 but we can go from state 1 to state 2 using the normal path of length 2 and then from state 2 to state 3 using the special path of length 2. So the total length will be 4, and we can clearly see that no other path can be smaller than this. Hence, the answer is 4.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the number of states and the number of paths, respectively.

The next ‘M’ lines contain four space-separated integers, ‘A’, ‘B’, ‘W1’, ‘W2’, denoting a normal path from ‘A’ to ‘B’ having a length ‘W1’ and a special path having a length ‘W2’.

The last line of each test case contains two space-separated integers, ‘X’ and ‘Y’, denoting the states between which the shortest distance has to be calculated.

Output Format:

For each test case, print an integer denoting the shortest path length between the two given states. 

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N < 10^3
N-1 <= M <= 10^3
1 <= A,B,X,Y <= N
1 <= W1,W2 <= 10^6

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

1
2

Explanation:

For test case 1:
A direct path exists from state 1 to state 2. The length will be 2 when we traverse from state 1 to state 2 using the normal path, but when we traverse using the special path, the length will be 1, which is less. Hence our answer is 1.

For test case 2:
A direct path exists from state 1 to state 3. The length will be 2 when we traverse from state 1 to state 3 using the normal path, but when we traverse using the special path, the length will be 4, which is more. Hence our answer is 2.

Sample Input 2:

Sample Output 2:

Approaches (1)

Approach 1

Special Paths

Time Complexity

Space Complexity

(100% EXP penalty)

Shortest Distance

Console