GATE CS 2020 Q.5 (GA Q.5): Quantitative Aptitude

There are multiple routes to reach from node 1 to node 2, as shown in the network.

Directed graph showing travel routes from node 1 to node 2 through toll booths a, b, c, d, e, and f with edge travel costs — Network of routes from node 1 to node 2

The cost of travel on an edge between two nodes is given in rupees. Nodes 'a', 'b', 'c', 'd', 'e', and 'f' are toll booths. The toll price at toll booths marked 'a' and 'e' is Rs. 200, and is Rs. 100 for the other toll booths. Which is the cheapest route from node 1 to node 2?

1-a-c-2

1-f-b-2

1-b-2

1-f-e-2

Official answer and solution

Official answer: B
From: Official GATE 2020 answer key

Solution

Calculate the total cost (edge travel cost plus applicable toll booth charges) for each candidate path from node 1 to node 2.

Toll prices: booths 'a' and 'e' cost Rs. 200 each. Booths 'b', 'c', 'd', and 'f' cost Rs. 100 each. Nodes 1 and 2 are terminal nodes and are not toll booths.

Evaluate the four given options:

Route 1-a-c-2: Edge costs = $200 + 100 + 100 = 400$ . Tolls = booth 'a' (200) + booth 'c' (100) = 300. Total cost = $400 + 300 = 700$ .
Route 1-f-b-2: Edge costs = $100 + 0 + 200 = 300$ . Tolls = booth 'f' (100) + booth 'b' (100) = 200. Total cost = $300 + 200 = 500$ .
Route 1-b-2: Edge costs = $300 + 200 = 500$ . Tolls = booth 'b' (100) = 100. Total cost = $500 + 100 = 600$ .
Route 1-f-e-2: Edge costs = $100 + 100 + 200 = 400$ . Tolls = booth 'f' (100) + booth 'e' (200) = 300. Total cost = $400 + 300 = 700$ .

Comparing the four routes, 1-f-b-2 has the lowest total cost of Rs. 500.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2020 Computer Science and Information Technology (CS)
Question: 5 of 65, printed as GA Q.5
Section: General Aptitude

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source