**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].

1 <= A <= 100000

1 <= |B| <= 100000

1 <= C, D <= A

1 <= |E| <= 300

All lengths of the roads lie between 1 and 1000.

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.

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

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] ]

Output 1:

2

Output 2:

-1

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.

Loading...