Six towns – P, Q, R, S, T and U – are connected by two-way roads. The matrix below gives the length (in km) of the direct road between two towns; '–' means that there is no direct road between them. Travel between towns is possible only along these roads, and a route may pass through intermediate towns.
| | P | Q | R | S | T | U |
|---|---|---|---|---|---|---|
| P | – | 40 | 65 | 90 | – | – |
| Q | 40 | – | 20 | – | 70 | – |
| R | 65 | 20 | – | 30 | 55 | – |
| S | 90 | – | 30 | – | 35 | 45 |
| T | – | 70 | 55 | 35 | – | 25 |
| U | – | – | – | 45 | 25 | – |
The 'shortest distance' between two towns means the length of the shortest route between them along the roads.
| | P | Q | R | S | T | U |
|---|---|---|---|---|---|---|
| P | – | 40 | 65 | 90 | – | – |
| Q | 40 | – | 20 | – | 70 | – |
| R | 65 | 20 | – | 30 | 55 | – |
| S | 90 | – | 30 | – | 35 | 45 |
| T | – | 70 | 55 | 35 | – | 25 |
| U | – | – | – | 45 | 25 | – |
The 'shortest distance' between two towns means the length of the shortest route between them along the roads.
Question 1
Numerical answer
What is the shortest distance (in km) between P and U?
Show answer and solution
Answer: 135
Shortest-distance table (computed by trying routes through intermediate towns):
| | P | Q | R | S | T | U |
|---|---|---|---|---|---|---|
| P | 0 | 40 | 60 | 90 | 110 | 135 |
| Q | 40 | 0 | 20 | 50 | 70 | 95 |
| R | 60 | 20 | 0 | 30 | 55 | 75 |
| S | 90 | 50 | 30 | 0 | 35 | 45 |
| T | 110 | 70 | 55 | 35 | 0 | 25 |
| U | 135 | 95 | 75 | 45 | 25 | 0 |
Note P–R is 60 via Q (40 + 20), shorter than the direct 65 km road.
P → Q → R → S → U = 40 + 20 + 30 + 45 = 135. Alternatives: P → S → U = 135 as well; via T: P → Q → R → T → U = 140. Minimum = 135 km.
| | P | Q | R | S | T | U |
|---|---|---|---|---|---|---|
| P | 0 | 40 | 60 | 90 | 110 | 135 |
| Q | 40 | 0 | 20 | 50 | 70 | 95 |
| R | 60 | 20 | 0 | 30 | 55 | 75 |
| S | 90 | 50 | 30 | 0 | 35 | 45 |
| T | 110 | 70 | 55 | 35 | 0 | 25 |
| U | 135 | 95 | 75 | 45 | 25 | 0 |
Note P–R is 60 via Q (40 + 20), shorter than the direct 65 km road.
P → Q → R → S → U = 40 + 20 + 30 + 45 = 135. Alternatives: P → S → U = 135 as well; via T: P → Q → R → T → U = 140. Minimum = 135 km.
Question 2
Single correct option
How many towns (other than R) are within a shortest distance of 60 km from R?
- A. 5
- B. 3
- C. 4
- D. 2
Show answer and solution
Answer: (C) 4
Shortest-distance table (computed by trying routes through intermediate towns):
| | P | Q | R | S | T | U |
|---|---|---|---|---|---|---|
| P | 0 | 40 | 60 | 90 | 110 | 135 |
| Q | 40 | 0 | 20 | 50 | 70 | 95 |
| R | 60 | 20 | 0 | 30 | 55 | 75 |
| S | 90 | 50 | 30 | 0 | 35 | 45 |
| T | 110 | 70 | 55 | 35 | 0 | 25 |
| U | 135 | 95 | 75 | 45 | 25 | 0 |
Note P–R is 60 via Q (40 + 20), shorter than the direct 65 km road.
From R: Q 20, S 30, T 55, P 60 (via Q), U 75. Within 60 km: Q, S, T, P → 4.
| | P | Q | R | S | T | U |
|---|---|---|---|---|---|---|
| P | 0 | 40 | 60 | 90 | 110 | 135 |
| Q | 40 | 0 | 20 | 50 | 70 | 95 |
| R | 60 | 20 | 0 | 30 | 55 | 75 |
| S | 90 | 50 | 30 | 0 | 35 | 45 |
| T | 110 | 70 | 55 | 35 | 0 | 25 |
| U | 135 | 95 | 75 | 45 | 25 | 0 |
Note P–R is 60 via Q (40 + 20), shorter than the direct 65 km road.
From R: Q 20, S 30, T 55, P 60 (via Q), U 75. Within 60 km: Q, S, T, P → 4.
Question 3
Single correct option
A courier starts from P, must visit every other town at least once, and must return to P. What is the minimum distance (in km) he must travel?
- A. 275
- B. 315
- C. 290
- D. 270
Show answer and solution
Answer: (D) 270
Shortest-distance table (computed by trying routes through intermediate towns):
| | P | Q | R | S | T | U |
|---|---|---|---|---|---|---|
| P | 0 | 40 | 60 | 90 | 110 | 135 |
| Q | 40 | 0 | 20 | 50 | 70 | 95 |
| R | 60 | 20 | 0 | 30 | 55 | 75 |
| S | 90 | 50 | 30 | 0 | 35 | 45 |
| T | 110 | 70 | 55 | 35 | 0 | 25 |
| U | 135 | 95 | 75 | 45 | 25 | 0 |
Note P–R is 60 via Q (40 + 20), shorter than the direct 65 km road.
Lower bound: any closed route from P that visits U must go from P to U and come back, so it is at least 2 × 135 = 270 km.
This bound is achieved: P → Q → R → S → U → T → Q → P = 40 + 20 + 30 + 45 + 25 + 70 + 40 = 270 km, and it visits every town.
Hence the minimum is 270 km. (A tour that visits each town exactly once using only direct roads needs 275 km, e.g. P-Q-T-U-S-R-P = 40 + 70 + 25 + 45 + 30 + 65.)
Tip: for 'visit all and return' questions, twice the distance to the farthest town is a quick lower bound.
| | P | Q | R | S | T | U |
|---|---|---|---|---|---|---|
| P | 0 | 40 | 60 | 90 | 110 | 135 |
| Q | 40 | 0 | 20 | 50 | 70 | 95 |
| R | 60 | 20 | 0 | 30 | 55 | 75 |
| S | 90 | 50 | 30 | 0 | 35 | 45 |
| T | 110 | 70 | 55 | 35 | 0 | 25 |
| U | 135 | 95 | 75 | 45 | 25 | 0 |
Note P–R is 60 via Q (40 + 20), shorter than the direct 65 km road.
Lower bound: any closed route from P that visits U must go from P to U and come back, so it is at least 2 × 135 = 270 km.
This bound is achieved: P → Q → R → S → U → T → Q → P = 40 + 20 + 30 + 45 + 25 + 70 + 40 = 270 km, and it visits every town.
Hence the minimum is 270 km. (A tour that visits each town exactly once using only direct roads needs 275 km, e.g. P-Q-T-U-S-R-P = 40 + 70 + 25 + 45 + 30 + 65.)
Tip: for 'visit all and return' questions, twice the distance to the farthest town is a quick lower bound.
Question 4
Single correct option
If the road between R and S is closed for repairs, what will be the shortest distance (in km) between Q and S?
- A. 105
- B. 85
- C. 130
- D. 110
Show answer and solution
Answer: (A) 105
Without R–S, the routes from Q to S are: Q → T → S = 70 + 35 = 105; Q → R → T → S = 20 + 55 + 35 = 110; Q → P → S = 40 + 90 = 130; Q → R → P → S = 20 + 65 + 90 = 175. Minimum = 105 km (earlier it was 50 km via R).
Saved on this device. Sign in or create a free account to keep it on every device.