3. Treasure Hunt: You are given a directed graph G=(V,E), where each node vEV in the graph has a certain amount of money m(v) >0 sitting on it. You are also given vertices st EV. The goal is to start at s and follow a directed path in G to reach t, picking up as much money along the way as you can. You may visit the same node more than once, but once you have picked up the money at that node, it is gone. Define M(G, m, s, t) to be the maximum money that can be picked up on any path from s to t (paths need not be simple). a) Show M(G, m, s, t) and a corresponding optimum st-path for the instance below. > 3 b) Design and analyze an efficient algorithm to compute M(G, m, s, t). (You are not required to compute the optimum st-path.) For full credit, your algorithm should run in time (V + E). [Hint: think about SCC.] You may continue your answer on the next page. 3. Treasure Hunt: You are given a directed graph G=(V,E), where each node vEV in the graph has a certain amount of money m(v) >0 sitting on it. You are also given vertices st EV. The goal is to start at s and follow a directed path in G to reach t, picking up as much money along the way as you can. You may visit the same node more than once, but once you have picked up the money at that node, it is gone. Define M(G, m, s, t) to be the maximum money that can be picked up on any path from s to t (paths need not be simple). a) Show M(G, m, s, t) and a corresponding optimum st-path for the instance below. > 3 b) Design and analyze an efficient algorithm to compute M(G, m, s, t). (You are not required to compute the optimum st-path.) For full credit, your algorithm should run in time (V + E). [Hint: think about SCC.] You may continue your answer on the next page