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, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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<int> &gFrom, vector<int> &gTo, vector<int> &gWeight, vector<int> &arr, int A, int B) {
    int E = gFrom.size();
    vector<pair<int,int>> adj[gNodes+1];
    for(int i=0;i<E;i++){
        adj[gFrom[i]].push_back({gTo[i],gWeight[i]});
        adj[gTo[i]].push_back({gFrom[i],gWeight[i]});
    }

    priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
    //cost,city,minPrice
    pq.push({0,{A,arr[A]}});
    vector<int> 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<cost[newCity]){
                cost[newCity] = currCost+dist*price;
                pq.push({cost[newCity],{newCity,price}});
            }
        }
    }
    if(cost[B]==INT_MAX) return -1;
    return cost[B];

}

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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<int> &gFrom, vector<int> &gTo, vector<int> &gWeight, vector<int> &arr, int A, int B) {
          int E = gFrom.size();
          vector<pair<int,int>> adj[gNodes+1];
          for(int i=0;i<E;i++){
              adj[gFrom[i]].push_back({gTo[i],gWeight[i]});
              adj[gTo[i]].push_back({gFrom[i],gWeight[i]});
          }
          priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
          //cost,city,minPrice
          pq.push({0,{A,arr[A-1]}});
          vector<int> 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<cost[newCity]){
                      cost[newCity] = currCost+dist*price;
                      pq.push({cost[newCity],{newCity,price}});
                  }
              }
          }
          if(cost[B]==INT_MAX) return -1;
          return cost[B];
      
      }