TopCoder problem "LongJourney" used in TCO10 Round 5 (Division I Level Two)

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.

Definition

Class:	LongJourney
Method:	minimumCost
Parameters:	int[], int, String[]
Returns:	long
Method signature:	long minimumCost(int[] fuelPrices, int fuelTank, String[] roads)
(be sure your method is public)

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}

{"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}

{"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}

{"0,2,50","0 2,3,50"}

Returns: -1

There is no way to get to the destination here.

{8131,12392,4152,7482,124208,1,1800,19,33791,2,4970,635157,7089,194,279,162627}

{"0,2,885843 0,5,948680 0,6,814375 0,7,254140 0,9,96"
,"5704 0,11,950391 0,12,2234 0,13,666704 0,14,757770"
," 1,4,233 1,5,850136 1,8,792847 1,9,62147 1,13,8726"
,"80 1,14,827511 1,15,253774 2,3,4831 2,4,63 2,5,660"
,"053 2,6,1079 2,7,379766 2,8,681543 2,9,910853 2,11"
,",871528 2,12,587492 2,13,762963 2,14,3761 3,4,3462"
,"62 3,5,147581 3,6,881103 3,8,426200 3,9,39902 3,10"
,",915751 3,11,293781 3,14,722019 3,15,394147 4,5,39"
,"5608 4,8,972273 4,9,855758 4,10,423924 4,12,974268"
," 4,15,931000 5,6,831319 5,7,76 5,8,53136 5,9,42289"
,"6 5,11,12626 5,13,220080 5,14,321058 5,15,6 6,7,51"
,"0462 6,10,926807 6,11,659470 6,12,702857 6,13,8555"
,"66 6,14,719994 6,15,868043 7,10,821770 7,13,216703"
," 7,15,758397 8,9,267740 8,10,772522 8,13,279514 9,"
,"10,24592 9,11,680535 9,12,624855 9,14,132484 10,15"
,",869307 11,12,28 11,13,493421 11,14,590457 12,14,3"
,"16607 13,14,542254"}

Returns: 108021568

{1000000,1000000}

{"0,1,1000000"}

Returns: 1000000000000

Be careful of overflow.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10678

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14283&pm=10678

Writer:

StevieT

Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

Problem categories:

Dynamic Programming, Graph Theory, Search