LongJourney

TCO10 Round 5 · 2010-04-11 · by StevieT

TCO10 Round 5 · 2010-04-11 · by StevieT · Dynamic Programming, Graph Theory, Search

Show categories

Class Name: LongJourney

Return Type: long

Method Name: minimumCost

Arg Types: (vector<int>, int, vector<string>)

Problem Statement

Alice is about to set out in her car on a long journey. Her car's fuel tank can only carry fuelTank units of fuel, so she may have to stop at gas stations along the way to refuel. Prices vary across different stations, so she needs to plan ahead to minimize the total cost of the journey.

The network of roads Alice is driving on is represented by an undirected graph with N nodes, in which she starts at node 0 and wishes to get to node 1. Initially, there is no fuel in her car's fuel tank. There is a fuel station located at each node and the cost per unit fuel at node i is fuelCost[i]. The graph is described by a String[] roads. The concatenation of the elements of roads forms a space-separated list of edges. Each edge is formatted "i,j,fuel" (quotes for clarity), in which i, j and fuel are integers formatted without leading zeros. This denotes that there is a bidirectional road connecting nodes i and j and fuel units of fuel will be consumed from the fuel tank in traversing this road. Alice doesn't want to end up stranded, so she cannot traverse a road with less than fuel units of fuel in the tank (although she can safely drive the road with exactly enough fuel).

Return the minimum cost of completing the journey or -1 if it is impossible to get from node 0 to node 1.

Notes

There is no limit to the amount of fuel that Alice can buy at each node.

Constraints

fuelPrices will contain between 2 and 50 elements, inclusive.
Each element of fuelPrices will be between 1 and 1000000 (10^6), inclusive.
fuelTank will be between 1 and 1000000 (10^6), inclusive.
roads will contain between 1 and 50 elements, inclusive.
Each element of roads will contain between 1 and 50 characters, inclusive.
The concatenation of the elements of roads will be a single-space-separated list of edges (as described in the problem statement), without leading or trailing spaces.
In each edge in roads, i and j will be between 0 and N-1, inclusive, where N is the number of elements in fuelTank.
In each edge in roads, i will be strictly less than j.
In each edge in roads, fuel will be between 1 and fuelTank, inclusive.
The i, j pairs of the edges in roads will be distinct.

Examples

{5,6,1,2}
100
{"0,2,2 "
,"0,3,5 "
,"1,3,3"}
Returns: 20

Here, the 4 fuel stops are spread along a single road: Station 2--0-----3---1 Price 1 5 2 6 Fuel is very cheap at station 2 and in an optimal trip Alice buys 2 units of fuel at station 0 for cost 10, then travels to station 2 and buys 10 units of fuel there for cost 10. She then drives to her final destination without stopping again.

{5,6,1,2}
100
{"0,2,2 "
,"0,3,1 "
,"1,3,7"}
Returns: 19

This is the same case as example 0, but with fuel station 3 moved in position along the road. Station 2--0-3-------1 Price 1 5 2 6 This time, it is cheaper to simply buy a unit of fuel at station 0, then drive to station 3 and buy the remaining fuel required there.

{10,15,5,20}
500
{"0,2,50","0 2,3,50"}
Returns: -1

There is no way to get to the destination here.

{364,400,121,40,13,4,1}
10000
{"0,2,1 "
,"0,3,2 "
,"0,4,4 "
,"0,5,8 "
,"0,6,16 "
,"0,1,32"}
Returns: 1267

{29524,1000000,9841,3280,1093,364,121,40,13,4,1}
1000000
{"0,2,1 "
,"0,3,2 "
,"0,4,4 "
,"0,5,8 "
,"0,6,16 "
,"0,7,32 "
,"0,8,64 "
,"0,9,128 "
,"0,10,256 "
,"0,1,512"}
Returns: 115027

113)

{1000000,1000000}
1000000
{"0,1,1000000"}
Returns: 1000000000000

Be careful of overflow.

Submissions are judged against all 129 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LongJourney with a public method long long minimumCost(vector<int> fuelPrices, int fuelTank, vector<string> roads) · 129 test cases · 2 s / 256 MB per case