The country of Hackerland is represented as a graph of g_nodes cities numbered from 1 to g_nodes. The cities are connected through g_edges bidirectional roads where the ith road connects city g_from[i] and city g_to[i] and the amount of fuel required to travel a road is g_weight[i] units. The cars in Hackerland have an infinite fuel capacity. The cost of one unit of fuel in the ith city is arr[i]. Any amount of fuel can be obtained in any city.

Given two cities A and B **(1<=A , B<=road_nodes)**, find the minimum cost to travel from city A to city B . If it is not possible, return -1.

**Example:**

```
g_nodes = 5
g_from = [4,5,4,1,3,4,4]
g_to = [1,3,5,5,1,2,3]
g_weight = [1,1,8,1,3,9,5]
arr = [9,11,3,2,10]
A = 3
B = 2
```

One optimal path is **3 --> 5 --> 1 --> 4 --> 2**. Buy 3 units of fuel at 3 with cost of 3*3 = 9 and 9 units at city 4 for 9*2=18. The total cost is 9+18 = 27

**Function Description:**

Complete the function getMinCost in the editor below.

getMinCost has the following parameters: int g_nodes: the number of cities int g_from[g_edges]: one endpoint of each road int g_to[g_edges]: the other endpoint of each road int g_weight[g_edges]: the weight of each road int arr[g_nodes]: the cost of unit fuel in each city int A: the city to start from int B: the destination city

**Returns:**

long int: the minimum cost to go from City A to City B, or -1 if it is impossible.

**Constraints:**

```
1) 2<=g_nodes<=200
2) 1<=g_edges<=g_nodes*(g_nodes-1)/2
3) 1<=g_from[i]<=g_nodes
4) 1<=g_to<=g_nodes
5) 1<=g_weight[i]<=10^6
6) 1<=arr[i]<=10^6
7) 1<=A,B<=g_nodes
```

**Complete the function given below:**

```
public static long getMinCost(int gNodes, List<Integer> gFrom, List<Integer> gTo, List<Integer> gWeight, List<Integer> arr, int A, int B) {
}
```

Someone please solve this question.

Whats the source? Is there any OJ where we can test our solution?

Unfortunately it's a private OJ, and hence not accessible.

Here is some random internet find. No idea if its correct code

https://notepad.link/G7ePi

Hello, this is a graph question so I used priority queue to solve it. While I can't verify that my solution is correct as you didn't link to any OJ, here's my solution:

(It is written in C++ so, feel free to ask if you don't understand anything or the solution is not accepted)

Hi dhairya. Thanks for the code. Much appreciated. But for the example input that I have provided, the expected output is 27. But your code is giving 26. Please rectify it. Thank you.

Well, the difference was because the adjacency list created by me is 1-indexed and the fuel prices array is also 1-indexed but stored from the index 0 in the provided array. Here's the modified code: