In Gridville, the POTW Delivery Company needs to deliver nine
packages to nine different locations. In the diagram below, the location
where they start is labelled with an \(S\). The nine other circles indicate where
the nine delivery locations are. These locations are joined by roads,
which are shown as lines. The number beside each line indicates the
average time, in minutes, it will take to travel along that road.
10 circles are arranged into 2 rows of 5.
The top-left circle is marked \(S\).
Each circle in the top row is connected by a line to the next circle
in the top row. The four connecting lines, from left to right, have
numbers \(3\), \(3\), \(4\), and \(6\).
Each circle in the top row is also connected by a line to the circle
directly below it in the bottom row. The five connecting lines, from
left to right, have numbers \(2\),
\(5\), \(1\), \(8\), and \(4\).
Each circle in the bottom row is connected by a line to the next
circle in the bottom row. The four connecting lines, from left to right,
have numbers \(1\), \(3\), \(2\), and \(5\).
If the POTW Delivery Company does not want to visit any location more
than once, but can finish at any location, what is the shortest amount
of time that they will take to deliver the nine packages?
