**Problem Description**

You are given the map of a city having **A** houses, in form of an undirected graph **B**, where **B[i]** denotes a road between
houses **B[i][0]** and **B[i][1]** having length **B[i][2]**.

For a given pair of houses **C** and **D**, You have to tell the shortest road that can exist in a shortest path between them.

**NOTE:** It is guaranteed that there exists always exists a path between **C** and **D**, i.e, they are always connected.

2 <= **A** <= 10^{5}

1 <= **|B|** <= 10^{6}

1 <= **A[i][0], A[i][1]** <= N

1 <= **A[i][2]** <= 10^{9}

**C** is not equal to **D**.

First argument is an integer **A**.

Second argument is a 2-D integer matrix **B**.

Third argument is an integer **C**.

Fourth argument is an integer **D**.

Return an integer denoting length of required shortest edge.

Input 1:

A = 7 B = [1 2 2] [2 3 8] [1 7 3] [7 4 2] [4 3 5] [1 5 3] [5 3 7] [1 6 1] C = 1 D = 3

Input 2:

A = 4 B = [1 2 1] [2 3 1] [1 3 2] [3 4 1] C = 2 D = 4

Output 1:

2

Output 2:

2

Explanation 1:

In the graph, we need to go from house 1 to house 3. None of the shortest path includes road [1 6 1], so it can never give the answer. There are 3 shortest paths between house 1 and house 3: 1) 1 -> 2 -> 3 = Total length = 10 2) 1 -> 5 -> 3 = Total length = 10 3) 1 -> 7 -> 4 -> 3 = Total length = 10 So, edges [1 2 2], [2 3 8], [1 5 3], [5 3 7], [1 7 3], [7 4 2] and [4 3 5] are each part of one of shortest paths between houses 1 and 3. Hence, the shortest road length in a shortest path = 2

Explanation 2:

There is only one shortest path betweenCandD: 2 -> 3 -> 4. The shortest road in the path has length = 1.

NOTE:You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.

- Hint 1
- Solution Approach
- Complete Solution

Loading...

Start Test