Question 3
The table below shows the travelling times (in hours) between the capital of a country and four other cities A, B, C, and D.
| | Capital | A | B | C | D |
|---|---|---|---|---|---|
| Capital | 0 | 12 | 25 | 8 | 9 |
| A | | 0 | 27 | 15 | 12 |
| B | | | 0 | 20 | 8 |
| C | | | | 0 | 19 |
| D | | | | | 0 |
For example, travelling from City A to City B takes 27 hours. Travelling from City B to City A also takes 27 hours.
Mr. Soh who is in the Capital wants to visit each city exactly once before going back to the Capital. What is the shortest possible time for his trip?
| | Capital | A | B | C | D |
|---|---|---|---|---|---|
| Capital | 0 | 12 | 25 | 8 | 9 |
| A | | 0 | 27 | 15 | 12 |
| B | | | 0 | 20 | 8 |
| C | | | | 0 | 19 |
| D | | | | | 0 |
For example, travelling from City A to City B takes 27 hours. Travelling from City B to City A also takes 27 hours.
Mr. Soh who is in the Capital wants to visit each city exactly once before going back to the Capital. What is the shortest possible time for his trip?