TopCoder problem "RoadReconstruction" used in SRM 356 (Division II Level Three)

Problem Statement

There are several cities in the country, and some of them are connected by bidirectional roads. Unfortunately, some of the roads are damaged and cannot be used right now. Your goal is to rebuild enough of the damaged roads that there is a functional path between every pair of cities.

You are given String[] roads, each element of which describes a single road. Damaged roads are formatted as "id city1 city2 cost" and non-damaged roads are formatted as "id city1 city2" (all quotes for clarity). In this notation, id is the unique identifier of the road, and city1 and city2 are the case-sensitive names of the two cities directly connected by that road. If the road is damaged, cost represents the price of rebuilding that road. Each id will be formatted "Cx" (quotes for clarity), where C is an uppercase letter and x is a digit. Every city in the country will appear at least once in roads.

Return a String containing a single space separated list of the identifiers of the roads that must be rebuilt to achieve your goal. If there are multiple possibilities, select the one with the minimal total reconstruction cost. If a tie still exists, return the String that comes first lexicographically. If it is impossible to achieve your goal, return "IMPOSSIBLE" (quotes for clarity only).

Definition

Class:	RoadReconstruction
Method:	selectReconstruction
Parameters:	String[]
Returns:	String
Method signature:	String selectReconstruction(String[] roads)
(be sure your method is public)

Notes

There can be more than one road between a pair of cities.

Constraints

roads will contain between 1 and 50 elements, inclusive.

Each element of roads will contain between 6 and 50 characters, inclusive.

Each element of roads will be formatted as "id city1 city2" or "id city1 city2 cost" (all quotes for clarity).

Each id will be formatted as "Cx" (quotes for clarity), where C is an uppercase letter ('A'-'Z') and x is a digit ('0'-'9').

Each id in roads will be distinct.

Each city1 and city2 will contain between 1 and 45 letters ('a'-'z', 'A'-'Z'), inclusive.

In each element of roads, city1 and city2 will be distinct.

Each cost will be an integer between 1 and 1000, inclusive, with no leading zeroes.

Examples

{"M1 Moscow Kiev 1", "M2 Minsk Kiev", "M3 Minsk Warsaw"}

Returns: "M1"

Rebuilding road M1 will make all three cities connected to each other.

{"R1 NY Washington", "M1 Moscow StPetersburg 1000"}

Returns: "IMPOSSIBLE"

Even after reconstuction of the road M1, the resulting road network won't be connected. So, the answer is "IMPOSSIBLE".

{"B1 Bratislava Havka"}

Returns: ""

{"M1 Moscow StPetersburg 1", "M2 Moscow Saratov 2", "S0 Saratov StPetersburg"}}

Returns: "M1"

{"O1 Beetown Fearnot 6","N7 Fearnot Hornytown","M8 Hornytown Belcher 10",
 "L5 Belcher Fearnot 8","C7 Fearnot Beetown 4","K7 Quiggleville Beetown 12",
 "H4 Beetown DryFork 6","Z0 Hornytown Belcher 1","O5 Belcher Quiggleville 10",
 "U7 Quiggleville Fearnot 2","A8 Fearnot Quiggleville 8","T6 Beetown DryFork 17",
 "E8 Quiggleville DryFork 8","Y4 DryFork Quiggleville 4","Q8 Hornytown DryFork 2",
 "J9 Quiggleville DryFork 19","M4 DryFork Quiggleville 7","T1 DryFork Fearnot 9",
 "G4 Fearnot DryFork 6","V9 Hornytown Beetown 5","O6 Quiggleville Beetown 4",
 "L8 Beetown Roachtown 5","D5 Belcher DryFork 8","W5 Belcher DryFork 1"}

Returns: "C7 L8 U7 W5 Z0"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7921

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10765&pm=7921

Writer:

Pawa

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Graph Theory, Sorting, String Parsing