This post is in reference to SPOJ

17660 The Bridge to Home WAYHOME.

You have a group of people on one side of a river, and it may only be crossed by a bridge; the bridge can take 1 or 2 at a time. All bridge-crossers must carry the lone flashlight, meaning each trip across must alternate — flashlight goes one way then back. Each person has a given “time to cross”, and two people crossing takes the longest time of the two. What is the minimum time (T) to cross?

e.g. You have times-to-cross of . So a solution is as follows:

across = 10

back = 3

across = 5

The algorithm has several cases as follows:

**1. Remaining <= 2:** simply cross

**2. Remaining == 3:** finish up, lo & mid, lo back, lo & hi

**3. Remaining > 3: ** shuttle two highest

lo = lowest

lo2 = 2nd lowest

hi2 = 2nd highest

hi = highest

N.B. Take the best of the two below. Using below for clarity.

**3a.** chauffeurs across, comes back and does the same for :

**3b.** chauffeurs and returns, and cross and (aha!) returns:

My solution is in git and below:

*Related*