Minimum time to cross the bridge

Question

There are 6 friends A, B, C, D, E and F who want to cross a bridge. However, there are two problems. First, the bridge can only accommodate two persons at a time. Second, it is night and they need the torch every time they cross the bridge (fortunately, they have one). The minimum time required by them to cross the bridge is 4 minutes, 2 minutes, 7 minutes, 11 minutes, 6 minutes and 1 minute, respectively. What is the minimum time in which they would be able to cross the bridge?
Options are -
28
29
30
31

RobPratt · Answer

You can solve this as a shortest path problem, as shown here.
For your data, the minimum is

attained as follows:
{B,F} cost = max(2,1)  = 2
{F}   cost = max(1)    = 1
{A,E} cost = max(4,6)  = 6
{B}   cost = max(2)    = 2
{B,F} cost = max(2,1)  = 2
{F}   cost = max(1)    = 1
{C,D} cost = max(7,11) = 11
{B}   cost = max(2)    = 2
{B,F} cost = max(2,1)  = 2

Shubham Goenka · Answer

There are a bunch of similar problems out there, but here's a specific detailed answer:

Minimum time to cross the bridge

2 Answers

Add your own answers!

Ask a Question