Uber OA 2023 - Uber HCVs (High Capacity Vehicles)

Problem Description

Uber HCVs (High Capacity Vehicles) run across the city of UberLand. UberLand has N stops where the HCVs pick up or drop the passengers. There is a network of M bidirectional roads that connect various stops. Each road has a particular length attached to it.

The Uber developers have introduced a weird feature of credits where each stop has some assigned credits C[i] (0 <= i < N) which the HCV can collect when it reaches the stop. These credits are used to travel on a road, and the number of credits used for traveling on a road is equal to the length of the road. So an HCV can travel on a road if it has credits equal to or more than the length of the road.

Input Format

• The first line contains an integer N, representing the number of stops in UberLand.
• The second line contains an array C of N integers, where C[i] represents the credits assigned to stop i.
• The third line contains an integer M, representing the number of roads.
• The next M lines each contain three integers X, Y, and Z representing a road between stops X and Y with a length of Z. ( X != Y ).
• The last two lines contain two integers, S (source stop) and D(destination stop).

Output Format

• Return the minimum distance that needs to be traveled from stop (S) to stop(D), or return -1 if it is not possible to reach the destination.

Constraints

• 1<=N<=50
• 0<=M<=100
• 0<=C[i]<=100
• 1<=Length of each road<=100

Sample Input

5
2 10 5 100 3
8
0 1 2
0 3 5
0 2 1
1 3 10
1 4 15
2 3 7
2 4 90
3 4 80
4

Sample Output

19