TopCoder problem "CommanderIdol" used in TCHS SRM 64 (Division I Level Three)

Problem Statement

You are the commander of a group of soldiers on a battlefield. There are several forts on that battlefield, and you and your soldiers are currently at fort 0. Your task is to send a soldier to each of the other forts to deliver some secret prototypes.

Your mission is considered complete when there is exactly one solider at each of the other forts. You want to complete the mission as soon as possible, but you also want to maintain your high popularity among your soldiers. You have noticed that allowing soldiers to sleep a couple of hours before beginning their missions will make you more popular with them. Specifically, if you let one soldier sleep for X hours before beginning his mission, you will gain X popularity points.

You are given a String[] roads, where the j-th character of the i-th element is '-' if no road exists between forts i and j, or a digit between '0' and '9' representing the number of hours it would take a soldier to travel between forts i and j. Return the maximum total number of popularity points you can gain while still completing the mission as quickly as possible. Return -1 if it is impossible to complete the mission.

Definition

Class:	CommanderIdol
Method:	getMaxPopularity
Parameters:	String[]
Returns:	int
Method signature:	int getMaxPopularity(String[] roads)
(be sure your method is public)

Constraints

roads will contain n elements, where n is between 2 and 50, inclusive.

Each element of roads will contain exactly n characters.

Each character in roads will be '-' or a digit between '0' and '9', inclusive.

Character i in element i of roads will be '-'.

Character i in element j of roads will be the same as character j in element i of roads.

Examples

{"-1-","1-2","-2-"}

Returns: 2

The mission will require at least 3 hours to be finished. You can allow the soldier assigned to fort 1 to sleep 2 more hours without delaying the mission completion.

{"-1--","1-2-","-2--","----"}

Returns: -1

There is no way for your soldiers to reach fort 3, so this mission cannot be accomplished.

{"--7-6",
 "----8",
 "7--51",
 "--5-7",
 "6817-"}

Returns: 17

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13533&pm=10197

Writer:

vexorian

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Graph Theory, Simple Math