InterviewBit Academy is now Scaler!
Learn Tech Skills from Scratch @ Scaler EDGE

Useful Extra Edges


Problem Description

Given a graph of A nodes. Also given the weighted edges in the form of array B.

You are also given starting point C and destination point D.

Also given are some extra edges in the form of vector E.

You need to find the length of the shortest path from C to D if you can use maximum one road from the given roads in E.

All roads are one way ie they go from B[i][0] to B[i][1].



Problem Constraints

1 <= A <= 100000

1 <= |B| <= 100000

1 <= C, D <= A

1 <= |E| <= 300

All lengths of the roads lie between 1 and 1000.



Input Format

First argument is the integer A.

Second argument is the vector of vectors B.

Third argument is the integer C.

Fourth argument is the integer D.

Fifth argument is the vector of vectors E.



Output Format

Return -1 if C is not reachable from D. Else return the shortest distance between them.



Example Input

Input 1:

 A = 3
B = [   [1, 2, 1]
        [2, 3, 2]
    ]
C = 1
D = 3
E = [   [1, 3, 2]
    ]

Input 2:

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



Example Output

Output 1:

 2

Output 2:

 -1



Example Explanation

Explanation 1:

 Use the direct edge from 1 to 3. It has shortest path from 1 to 3.

Explanation 2:

 4 cannot be reached from 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 doubt? Checkout Sample Codes for more details.
Start solving Useful Extra Edges on Interview Code Editor
Hints
  • Hint 1
  • Solution Approach
  • Complete Solution
Asked In:

Discussion


Loading...
Click here to start solving coding interview questions