PROBLEM STATEMENT
NOTE: This problem statement contains images that may not display properly if viewed outside of
the applet.
You are playing a game titled Grand Slime Auto. You're playing as a mafioso in Slime City.
Slime City consists of N districts, numbered 0 through N-1, with some bidirectional roads
connecting pairs of districts. There are also some cars in the city. The i-th car is located in
district cars[i]. Note that there may be multiple cars in a district.
Today, you're going to collect protection money from several shops. You've decided on the order in
which you want to collect the money. This order is given in the vector districts. You will
first collect money from a shop in district districts[0]. You will then collect money from a shop
in district districts[1], and so on. The same district might appear multiple times in your list.
You are initially located in district 0.
You have two modes of transportation in Slime City: walking and driving. The time required to
traverse a road by walking is inverseWalkSpeed * the length of the road. The time required to
traverse a road by car is inverseDriveSpeed * the length of the road. When you're located in a
district that contains a car, you can steal that car and drive it wherever you want. However, the
rate of car theft in Slime City is so high that the moment you step out of the car, it will be
stolen and you won't be able to use it again. Note that you must get out of the car in order to
collect money from a shop.
The roads in Slime City are described in the vector roads, which contains N elements. The
j-th character of the i-th element of roads will be one of these :
'.' : no road connects districts i and j
Otherwise, a road connects districts i and j, and its length corresponds to character roads[i][j]:
'0'-'9' : 1-10
'a'-'z' : 11-36
'A'-'Z' : 37-62
Assuming that collecting money takes no time, return the minimum time required to collect all the
money from the shops.
DEFINITION
Class:SlimeXGrandSlimeAuto
Method:travel
Parameters:vector , vector , vector , int, int
Returns:int
Method signature:int travel(vector cars, vector districts, vector roads, int
inverseWalkSpeed, int inverseDriveSpeed)
CONSTRAINTS
-cars will contain between 1 and 50 elements, inclusive.
-Each element of cars will be between 0 and N-1, inclusive, where N is the number of elements in
roads.
-districts will contain between 1 and 50 elements, inclusive.
-Each element of districts will be between 0 and N-1, inclusive, where N is the number of elements
in roads.
-No two consecutive elements in districts will be equal.
-districts[0] will not be 0.
-roads will contain between 2 and 50 elements, inclusive.
-Each element of roads will contain N characters, where N is the number of elements in roads.
-Each character in roads will be '.', 'a'-'z', 'A'-'Z', or '0'-'9'.
-The j-th character of the i-th element of roads will be the same as the i-th character of the
j-th element of roads.
-The i-th character of the i-th element of roads will be '.'.
-Slime City will be connected, i.e., it will be possible to go from a district to any other
district through a series of roads.
-inverseWalkSpeed will be between 2 and 100, inclusive.
-inverseDriveSpeed will be between 1 and 99, inclusive.
-inverseWalkSpeed will be strictly greater than inverseDriveSpeed.
EXAMPLES
0)
{1}
{2,3,0}
{
"..0.",
"...1",
"0..2",
".12."}
5
1
Returns: 36
From district 0, walk to district 2 and collect money there. From district 2, walk to district 3
and collect money there. Now walk to district 1 and drive the car to district 0. Get out of the
car and collect money there. The total time spent is 5 * 1 + 5 * 3 + 5 * 2 + 1 * 2 + 1 * 3 + 1 * 1
= 36.
1)
{1}
{2, 0}
{
".A.",
"A.B",
".B."}
2
1
Returns: 262
From district 0, walk to district 1. Drive the car there to district 2. Get out of the car and
collect money there. Then, walk from district 2 to district 1 to district 0. Finally, collect
money there. The total time is : 37 * 2 + 38 * 1 + 38 * 2 + 37 * 2 = 262.
2)
{2,2}
{1,2,1}
{
".a4",
"a..",
"4.."}
3
1
Returns: 95
There may be multiple cars in a district, and you may wish to collect money from a district
multiple times.
3)
{1}
{2, 0}
{
".B.",
"B.A",
".A."}
2
1
Returns: 262
4)
{2,5,1,2}
{1,5,1,2,4}
{
".12.4.",
"1....7",
"2..3..",
"..3..5",
"4.....",
".7.5.."}
53
37
Returns: 1259
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.