0
$\begingroup$

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

$\endgroup$
1
1
$\begingroup$

You can solve this as a shortest path problem, as shown here.

For your data, the minimum is

29

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
$\endgroup$
0
$\begingroup$

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

Round 0 -> Starting:
- Left side = 1, 2, 4, 6, 7, 11
- Right side = None
- Total time = 0 minutes

Round 1 -> 1 and 2 cross, 1 comes back:
- Left side = 1, 4, 6, 7, 11
- Right side = 2
- Total time = 0 + 2 + 1 = 3 minutes

Round 2 -> 7 and 11 cross, 2 comes back:
- Left side = 1, 2, 4, 6
- Right side = 7, 11
- Total time = 3 + 11 + 2 = 16 minutes

Round 3 -> 1 and 2 cross, 1 comes back:
- Left side = 1, 4, 6
- Right side = 2, 7, 11
- Total time = 16 + 2 + 1 = 19 minutes

Round 4 -> 4 and 6 cross, 2 comes back:
- Left side = 1, 2
- Right side = 4, 6, 7, 11
- Total time = 19 + 6 + 2 = 27 minutes

Round 5 -> 1 and 2 cross:
- Left side = None
- Right side = 1, 2, 4, 6, 7, 11
- Total time = 27 + 2 + 0 = 29 minutes

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.