1 Robot Delivery

A robot is delivering products for a company in a city with a only one-way streets. The robot is required to deliver to at least one household on every street and then return to its original destination for refit and repair. The city charges the robot a small fee per street that it traverses; this fee is charged every time that the robot crosses from one intersection to the next. Fees vary depending on the street, but every street that the robot is allowed to travel on requires a fee of at least 1; any streets that have 0 fee mean that the robot is not allowed to travel there. The robots goal is to minimize the total fees that it is charged for delivering all of its products, respecting the constraints.

2 Input/Output

The first line of the input file (input.txt) will hold the number n of intersections in the city. What follows will be an n n adjacency matrix. Any 0 (i,j) entry in the adjacency matrix indicates that you cannot cross from intersection i to intersection j. A nonzero (i,j) entry will represent the fee that it costs to travel from intersection i to intersection j.

The intersections are numbered from 0 to n 1.

You may choose any cycle of minimum total fee as long as it starts and ends at the same intersection.

Your output will be a sequence of integers from 0 to n1 with a space after each.

3 Example

The input file (input.txt) may look like the following:

5

0 22566 46247 86550 85679

0 0 17214 0 0

1

77002 0 0 31972 0

0 0 0 0 12066

63767 0 0 6302 0

The output file (output.txt) could look like the following (and remember that there will be multiple correct answers for any given input):

0 4 3 4 0 3 4 0 2 3 4 0 1 2 0

2