PROBLEM STATEMENT
A shuttle bus services a ferry terminal. The bus goes around the city in loops,
picks up the passengers, and brings them to the ferry terminal. The shuttle bus
has many designated stops around the city, but only a few stops actually have
passengers waiting for the bus at any given time. Before the bus departs from
the terminal, the dispatcher gives the driver a list of all the stops with
passengers (passengers call dispatchers and let them know where they are). The
driver needs to design the shortest loop to pick up all the passengers waiting
for the bus.
DEFINITION
Class name: ShuttleBus
Method name: minLoop
Parameters: String[], int[]
Return type: int
Method signature (be sure your method is public): int minLoop (String[] map,
int[] passengers);
Each entry in the map represents one bus stop - it specifies the distances to
the bus stops connected to this one with direct routes. Entries are formatted
as follows (here and below quotation marks are for clarity only):
"STOP:DISTANCE STOP:DISTANCE ... STOP:DISTANCE"
STOP is the index in the map of the bus stop to which there is a direct route;
DISTANCE is the length of that route. The STOP:DISTANCE groups are separated by
one or more ' ' (space) characters. Entries of the map may have leading and/or
trailing spaces - your method should ignore them.
int[] passengers specify the indexes of the bus stops with waiting passengers.
There will be up to seven stops with passengers.
The bus starts at the stop 0, which is the ferry terminal. The method returns
the length of the shortest loop required to pick up all passengers, and return
back to the ferry terminal (bus stop 0). If there is no loop connecting all the
bus stops with passengers, the method should return -1.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- map has 1 to 50 entries, inclusive,
- Each map entry is 0 to 50 characters in length, and is formatted as described
above,
- The values of STOP in each map entry reference only existing map entries,
- The values of STOP in an entry do not refer back to the same stop,
- There are no duplicate STOP values in the same map entry (for example, "0:1
0:2" is an illegal entry),
- Each bus station has 0 to (N-1), inclusive, direct routes leaving from it,
where N is the size of the map,
- The values of DISTANCE in each map entry are in the range from 1 to 99,
inclusive,
- passengers has 1 to 7 entries, inclusive,
- passengers does not contain duplicate or invalid (out of the map) entries,
- passengers does not contain 0 - the index of the bus stop that corresponds to
the ferry terminal.
NOTES
- The shortest loop does not necessarily need to visit all the bus stops - it
may, but does not have to, skip the stops with no passengers.
- Some of the streets connecting bus stops may be one-way. See example 3.
- If there is a direct route from a bus stop A to a bus stop B, and another
direct route from the bus stop B to the bus stop A, the lengths of these two
routes are not necessarily identical. See example 3.
- When there are no routes leaving from a bus stop, the corresponding map entry
is an empty String "" (see example 5).
EXAMPLES
1. Consider the following city map (all streets are two-way streets; horizontal
and vertical lines represent streets of length 10, diagonal lines represent
streets of length 14).
0---1---2
| \ | / |
3---4---5
This corresponds to the following map:
{ "1:10 3:10 4:14",
"0:10 2:10 4:10",
"1:10 4:14 5:10",
"0:10 4:10",
"0:14 1:10 2:14 3:10 5:10",
"2:10 4:10" }
If passengers={1}, your method should return 20; the loop is 0-1*-0 (here and
below '*' denotes bus stops with passengers).
If passengers={1,4}, your method should return 34, the loop is 0-1*-4*-0.
If passengers={1,2,4,5}, your method should return 54, the loop is
0-1*-2*-5*-4*-0.
If passengers={1,2,3,4,5}, your method should return 60, the loop is
0-1*-2*-5*-4*-3*-0.
2. Consider the following city map (all streets are two-way streets; horizontal
and vertical lines represent streets of length 10, diagonal lines represent
streets of length 14).
0---1---2---3---4
| \ | | / | \ |
5---6 7 8---9
| / | / | \ | / |
10--11--12--13--14
This corresponds to the following map:
{ "1:10 5:10 6:14",
"0:10 2:10 6:10",
"1:10 3:10 7:10",
"2:10 4:10 7:14 8:10 9:14",
"3:10 9:10",
"0:10 6:10 10:10",
"0:14 1:10 5:10 10:14 11:10",
"2:10 3:14 11:14 12:10 13:14",
"3:10 9:10 13:10",
"3:14 4:10 8:10 13:14 14:10",
"5:10 6:14 11:10",
"6:10 7:14 10:10 12:10",
"7:10 11:10 13:10",
"7:14 8:10 9:14 12:10 14:10",
"9:10 13:10" }
If passengers={6,7,14}, your method should return 108, an example loop is
0-1-2-7*-13-14*-13-12-11-6*-0.
If passengers={1,7,5}, your method should return 74, an example loop is
0-1*-2-7*-11-10-5*-0.
If passengers={2,3,4,7,8,9,11}, your method should return 122, an example loop
is 0-6-11*-7*-13-8*-9*-4*-3*-2*-1-0.
If passengers={3,10,11,12,13}, your method should return 100, an example loop
is 0-1-2-3*-8-13*-12*-11*-10*-5-0.
3. Here is an asymmetric example:
The map= {
"1:3 3:8 7:10",
"2:2 4:3 5:4",
"0:6 3:7 5:3 6:4",
"0:8 2:7 6:2 8:9",
"1:4 7:4",
"3:2 7:3 9:5",
"2:3 3:3 9:2",
"2:6 5:4",
"6:2 7:3",
"5:5 8:2" }
If passengers={1,2,3}, your method should return 18.
If passengers={4,6,7}, your method should return 27.
If passengers={3,4,5,6,7,8,9}, your method should return 33.
4. Consider the following (disconnected) city map (all streets are two-way
streets; horizontal lines represent streets of length 10).
0---1 2---3
This corresponds to the following map: { "1:10", "0:10", "3:10", "2:10"}
If passengers={1}, your method should return 20, the loop is 0-1*-0.
If passengers={2,3}, your method should return -1, because there is no path
from the ferry terminal (0) to bus stops 2 and 3.
5. Consider the case when the map= {" 1:10 ", " "}. There is a single one-way
street from the ferry terminal to the bus stop 1. If passengers={1}, your
method should return -1.