Connection Status:
Competition Arena > RoadReconstruction

RoadReconstruction

SRM 356 · 2007-07-02 · by Pawa

SRM 356 · 2007-07-02 · by Pawa · Graph Theory, Sorting, String Parsing
Class Name: RoadReconstruction
Return Type: String
Method Name: selectReconstruction
Arg Types: (vector<string>)
Problem Statement

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).

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
0)
{"M1 Moscow Kiev 1", "M2 Minsk Kiev", "M3 Minsk Warsaw"}
Returns: "M1"

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

1)
{"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".

2)
{"B1 Bratislava Havka"}
Returns: ""
3)
{"M1 Moscow StPetersburg 1", "M2 Moscow Saratov 2", "S0 Saratov StPetersburg"}
Returns: "M1"
4)
{"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"

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

Coding Area

Language: C++17 · define a public class RoadReconstruction with a public method string selectReconstruction(vector<string> roads) · 50 test cases · 2 s / 256 MB per case

Submitting as anonymous