SlimeXGrandSlimeAuto

SRM 506 · 2010-11-01 · by dolphinigle

SRM 506 · 2010-11-01 · by dolphinigle · Graph Theory

Show categories

Class Name: SlimeXGrandSlimeAuto

Return Type: int

Method Name: travel

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

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 int[] 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 String[] 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.

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

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

{1}
{2, 0}
{
".B.",
"B.A",
".A."}
2
1
Returns: 262

{2,5,1,2}
{1,5,1,2,4}
{
".12.4.",
"1....7",
"2..3..",
"..3..5",
"4.....",
".7.5.."}
53
37
Returns: 1259

{
1,5,3,1,7,
4,2,3,1,6,
7,7,4,4,2,
2,3,1,5,1,
4,2,3,5,6,
1,2,3,4,5,
5,4,3,2,1,
1,2,1,5,6,
7,7,7,7,7,
1,2,3,4,5}
{
41,5,33,11,27,
4,2,33,21,16,
47,42,34,14,12,
32,13,41,25,21,
34,12,43,25,6,
31,12,43,14,5,
45,24,43,32,1,
41,22,21,25,6,
17,27,17,16,7,
21,22,43,44,5}
{
".AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"A.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AAA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AA",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.A",
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA."}
99
14
Returns: 157990

A big test case

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

Coding Area

Language: C++17 · define a public class SlimeXGrandSlimeAuto with a public method int travel(vector<int> cars, vector<int> districts, vector<string> roads, int inverseWalkSpeed, int inverseDriveSpeed) · 263 test cases · 2 s / 256 MB per case