Juspay OA-9 2023

Problem Description

JS newbie A wants to learn React from B and wants to figure out who in his network can introduce him to B in the shortest time period. The social network is modeled as a directed graph where:

• N is the total number of members in the network.
• Each member has an ID: MemberID_1, MemberID_2, MemberID_N.
• There are E edges (connections between members) that define who follows whom and how long it takes for a message to be passed between members.

You need to find the shortest time it will take for A to send a message through his network to B.

Input Format:

1. The first line contains an integer N, which represents the total number of members in the network.
2. The next N lines each contain an integer, representing the Member ID of each member.
3. The next line contains an integer E, representing the total number of edges (possible connections) in the network.
4. The next E lines each contain three integers p_i, q_i, and t_i, representing:
   • p_i: The ID of the member who is following someone (the source of the connection).
   • q_i: The ID of the member being followed (the destination of the connection).
   • t_i: The time taken to send a message from p_i to q_i.
5. The last two lines contain:
   • The Follower (JS newbie A’s ID).
   • The Following (React expert B’s ID).

Output Format:

• A single integer denoting the shortest time it takes for A to reach B through the network of friends. If A cannot reach B, return -1.

Constraints:

• 1 ≤ N ≤ 1000
• 1 ≤ E ≤ 10000
• 1 ≤ p_i, q_i ≤ N
• 1 ≤ t_i ≤ 100

Sample Input:

4
2
5
7
9
4
292
723
797
951
7
9

Sample Output:

5