Shortest Road Trip. Mary and Tom are taking a road trip from New York City to San Francisco. Because it is a 44-hour drive, Mary and Tom decide to switch off driving at each rest stop they visit. However, because Mary has a better sense of direction than Tom, she should be driving both when they depart and when they arrive (to navigate the city streets). Given a route map represented as a weighted directed graph G = (V, E) with positive edge lengths (the length of edge e is `e > 0), where vertices represent rest stops and edges represent routes between rest stops, devise an efficient algorithm to find a route (if possible) of minimum distance between New York City and San Francisco such that Mary and Tom alternate edges and Mary drives the first and last edge.

Hint: think how to modify either the shortest path computation or the problem input to account for alternating driving.