PROBLEM STATEMENT
Even though it is June, the city of SnowVille is facing some serious trouble: last night, lots of
snow covered all the roads in the city.
The road network looks as follows: There are N important places in the city. The places are
labeled 0 through N-1. Each road in the city connects two of these places. Each pair of places is
connected by at most one road. Each road can contain one or more car lanes. Each road is
bidirectional and the number of lanes is the same for both directions.
Sadly, all the snow plows except for one were already decommissioned for the summer.
The one snow plow that is still available is in a depot at place 0.
Whenever the snow plow drives along a road, it is able to clean a single lane going in the
direction in which it travels.
Hence if you want to clean an entire road with K lanes going in each direction, the snow plow must
drive along this road at least K times in each direction.
You are given a vector roads that describes the road network:
If there is no road between places i and j, character j of element i of roads is '0'.
The maximum number of lanes a road can have in each direction is 9.
If there is a road with k lanes in each direction, character j of element i of roads is 'k' (that
is, '1' if there is one lane, '2' if there are two lanes, etc.)
Traversing a single lane of any single road takes the snow plow exactly one minute. Return the
least number of minutes in which the snow plow can clean all lanes on all roads.
If cleaning all lanes on all roads is impossible, return -1 instead.
DEFINITION
Class:SnowPlow
Method:solve
Parameters:vector
Returns:int
Method signature:int solve(vector roads)
NOTES
-The snow plow is allowed to drive along a lane it already cleared.
-The road network does not have to be planar.
CONSTRAINTS
-The number of places N will be between 2 and 50, inclusive.
-roads will contain exactly N elements.
-Each element of roads will contain exactly N characters.
-Each character of each element of roads will be between '0' and '9', inclusive.
-roads will be symmetric, i.e., for each i and j: character i of element j of roads will be equal
to character j of element i of roads.
-For each i, character i of element i of roads will be '0'.
EXAMPLES
0)
{"010000",
"101000",
"010100",
"001010",
"000101",
"000010"}
Returns: 10
The important places are connected as follows: 0-1-2-3-4-5. The only optimal solution is for the
snow plow to travel from 0 to 5 and back.
1)
{"010000",
"101000",
"010100",
"001020",
"000201",
"000010"}
Returns: 12
This time the road between places 3 and 4 has two lanes in each direction. One possible optimal
schedule for the snow plow is to visit the places in the order 0,1,2,3,4,5,4,3,4,3,2,1,0, each
time using a new lane.
2)
{"031415",
"300000",
"100000",
"400000",
"100000",
"500000"}
Returns: 28
This time the snow plow can clean all lanes simply by going back and forth between 0 and each of
the neighboring places a suitable number of times.
3)
{"0100",
"1000",
"0001",
"0010"}
Returns: -1
There is no way to reach the road 2-3, so clearly there is no solution.
4)
{"0101",
"1001",
"0000",
"1100"}
Returns: 6
In this case the road network consists of the roads 0-1, 0-3, and 1-3. It can be cleared for
example by doing a circle in one direction (0-1-3-0) followed by a circle in the other direction.
Note that place 2 remains unvisited.
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.