CEMC Banner

Problem of the Week
Problem E
Special Delivery

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.

A description of the diagram follows.

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?