PrepRung
Sign inSign up free

CAT 2016 Slot 2 · DILR · Networks and Routes · hard

CAT 2016 Slot 2 DILR: Inter-Town Route Network

A logistics company is planning road links among six towns — P, Q, R, S, T and U. The table below lists every road route that can feasibly be built between a pair of towns, along with its construction cost. Not every pair of towns has a feasible direct route; travel between unlisted pairs must go via other towns along the listed routes.

| Route | Cost (₹ lakh) |
|---|---|
| P-Q | 4 |
| P-R | 8 |
| Q-R | 6 |
| Q-S | 5 |
| R-S | 2 |
| R-U | 9 |
| S-T | 3 |
| S-U | 7 |
| T-U | 4 |

Question 1

Numerical answer

What is the minimum total cost (in ₹ lakh) of building a network of routes that connects all six towns (directly or indirectly)?
Show answer and solution

Answer: 18

This is a minimum spanning tree problem. Adding routes in increasing order of cost while avoiding cycles: R-S(2), S-T(3), P-Q(4), T-U(4), Q-S(5) — these 5 routes connect all 6 towns without a cycle, costing 2+3+4+4+5 = 18. Any other combination either fails to connect all towns or costs more.

Question 2

Numerical answer

What is the minimum cost (in ₹ lakh) of travelling from P to U using the listed routes (possibly via other towns)?
Show answer and solution

Answer: 16

Check paths from P to U: P-Q-S-U = 4+5+7 = 16; P-Q-S-T-U = 4+5+3+4 = 16; P-R-U = 8+9 = 17; P-R-S-U = 8+2+7 = 17. The cheapest is 16 (achieved via P-Q-S-U or P-Q-S-T-U).

Question 3

Numerical answer

What is the minimum cost (in ₹ lakh) of travelling from Q to U using the listed routes?
Show answer and solution

Answer: 12

From Q, the cheapest paths to U are Q-S-U = 5+7 = 12 and Q-S-T-U = 5+3+4 = 12, both costing 12, which is cheaper than Q-R-U = 6+9 = 15.

Question 4

Single correct option

If the route R-S becomes unusable, what is the new minimum cost (in ₹ lakh) of a network connecting all six towns?
  1. A. 18
  2. B. 20
  3. C. 22
  4. D. 24
Show answer and solution

Answer: (C) 22

Without R-S, build the spanning tree from remaining routes in increasing cost: S-T(3), P-Q(4), T-U(4), Q-S(5), Q-R(6) — these connect all six towns without a cycle, costing 3+4+4+5+6 = 22. (R-U at 9 is not needed since Q-R already links R.)
Report a mistake

Original question written in the CAT 2016 Slot 2 pattern and checked twice for the correct answer. Not an official question paper. How we write and check questions · Corrections policy · Report a mistake