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.