a bit of greedy: UVa 10037 - Bridge

Problem Statement
UVa 10037 - Bridge

Summary:
(A very famous puzzle actually) \(N\) people trying to cross the bridge with one flashlight. Only groups with at most \(2\) people can cross the bridge, and a group has to carry flashlight in order to cross. Each person has a speed, which is the time needed for him to cross the bridge. Furthermore, the time needed for a group to cross the bridge is as fast as the slowest person in that group. Find the minimum time needed to cross everyone off to the other side.

Solution:
There is a greedy "intuition" (or is it? :( ) as follows:

/* 
Suggested Greedy algo: Incremental construction:
The idea is to always bring the first and second slowest to the other side
with the help of the first and second fastest 
say the fastests are A<B
and the slowest are X>Y
then we have 2 cases:
1. M = (A,X) + (A,0) + (A,Y) + (A,0)
   M = 2*A + X + Y
2. M' = (A,B) + (A,0) + (X,Y) + (B,0)
   M' = 2*B + A + X
And incrementally choosing the minimum of M and M' at each step.
Proof? I dont know
*/

The proof to the intuition is somewhat more elaborate, by representing the problem as a graph problem.