Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

yashsaha555's blog

By yashsaha555, 2 months ago,

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.

Refer to this image

• 0

 » 2 months ago, # |   0 Whats the source? Is there any OJ where we can test our solution?
•  » » 2 months ago, # ^ |   0 Unfortunately it's a private OJ, and hence not accessible.
•  » » » 2 months ago, # ^ |   0 Here is some random internet find. No idea if its correct codehttps://notepad.link/G7ePi
 » 2 months ago, # | ← Rev. 2 →   0 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: long long getMinCost(int gNodes, vector &gFrom, vector &gTo, vector &gWeight, vector &arr, int A, int B) { int E = gFrom.size(); vector> adj[gNodes+1]; for(int i=0;i>,vector>>,greater>>> pq; //cost,city,minPrice pq.push({0,{A,arr[A]}}); vector cost(gNodes+1,INT_MAX); cost[A] = 0; while(!pq.empty()){ auto i = pq.top(); pq.pop(); int currCost = i.first; int city = i.second.first; int minPrice = i.second.second; for(auto it:adj[city]){ int newCity = it.first; int dist = it.second; int price = min(minPrice,arr[city]); if(currCost+dist*price
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 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: long long getMinCost(int gNodes, vector &gFrom, vector &gTo, vector &gWeight, vector &arr, int A, int B) { int E = gFrom.size(); vector> adj[gNodes+1]; for(int i=0;i>,vector>>,greater>>> pq; //cost,city,minPrice pq.push({0,{A,arr[A-1]}}); vector cost(gNodes+1,INT_MAX); cost[A] = 0; while(!pq.empty()){ auto i = pq.top(); pq.pop(); int currCost = i.first; int city = i.second.first; int minPrice = i.second.second; for(auto it:adj[city]){ int newCity = it.first; int dist = it.second; int price = min(minPrice,arr[city-1]); if(currCost+dist*price