Question

While staying in Rome, Italy, you decide to take a trip to three other cities: Milan, Genoa, and Padua. The following table details the costs of traveling to and from each city. All costs given are in euros (€).

Origin and Destination
Cost (€)
Rome to Milan
71
Rome to Genoa
52
Rome to Padua
61
Milan to Rome
74
Milan to Genoa
59
Milan to Padua
68
Genoa to Rome
76
Genoa to Milan
56
Genoa to Padua
58
Padua to Rome
68
Padua to Milan
67
Padua to Genoa
54

Determine the cost of the most efficient route. You may visit the cities in any order, but you must start and end in Rome.
a.
€256
b.
€251
c.
€244
d.
€238

Answer 1

Compute the total cost for each permutation of visits (start/end at Rome):

- Rome → Milan → Genoa → Padua → Rome = 71 + 59 + 58 + 68 = €256
- Rome → Milan → Padua → Genoa → Rome = 71 + 68 + 54 + 76 = €269
- Rome → Genoa → Milan → Padua → Rome = 52 + 56 + 68 + 68 = €244
- Rome → Genoa → Padua → Milan → Rome = 52 + 58 + 67 + 74 = €251
- Rome → Padua → Milan → Genoa → Rome = 61 + 67 + 59 + 76 = €263
- Rome → Padua → Genoa → Milan → Rome = 61 + 54 + 56 + 74 = €245

The cheapest route is Rome → Genoa → Milan → Padua → Rome with cost €244.

Answer: c. €244.