Programming Assignment 3
2 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 robot’s goal is to minimize the total fees that
it is charged for delivering all of its products, respecting the constraints.
3 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 n−1 with a space after
each.
4 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
