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 € 244

Let R stand for Rome, M stand for Milan, G stand for Genoa and P stand for Padua.

Total number of possible routes are 6, which are as follows:

1) R→G→M→P→R

2) R→G→P→M→R

3) R→M→G→P→R

4) R→M→P→G→R

5) R→P→M→G→R

6) R→P→G→M→R

Thus, the possible costs for all the routes (in €) are:

1) R→G→M→P→R = 52+56+68+68 = 244

2) R→G→P→M→R = 52+58+67+74 = 251

3) R→M→G→P→R = 71+59+58+68 = 256

4) R→M→P→G→R = 71+68+54+76 = 269

5) R→P→M→G→R = 61+67+59+76 = 263

6) R→P→G→M→R = 61+54+56+74 = 245

Thus, the most efficient route is R→G→M→P→R i. e Rome to Genoa to Milan to Padua to Rome as the cost is the least € 244.

Hence, the correct option is c. €244.