# The Bridge to Home

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: