Consider a directed graph G = (V, E) that captures the road network in your city. You live at vertex s V . Each edge e has a positive length l(e) > 0. Further, there are gift stores at a subset S V of vertices. Your friends live at another subset F V of vertices. For each vertex v in F, you would like to know the shortest path from s to v stopping by at least one gift stores on its way. Design an algorithm for this problem, and analyze its correctness and running time.

(You get up to 20 points for giving a correct polynomial-time algorithm. To get all 25 points, your algorithms running time must be O((V + E) log V ) or better.)