1. Consider the following graph: Petrol cost start 22 70 50 50 12 10 50 70 20 15 30 D G 80 25 10 18 10 70 10 18 70 13, E 70 8 H 15 10 Hotel cost C 80 60 60 The problem is to find the minimum cost of travelling on vacation from home (start) to any of the resorts (JKL) at the destination. You are allowed a stopover at each of the stages (3 stopovers) before you reach your destination. Your choice of routes will depend on petrol and hotel costs, which add up to minimum overall cost. Based on several techniques discussed in class: A) (10 points) Identify a good algorithm design technique that will result to optimal solution for this problem. Give a brief explanation why the choice will be a viable solution technique. B) (10 points) Write the optimal function/definition of the solution in terms of subproblem solutions. C) (10 points) If the computational complexity analysis of this problem requires significant time, is there any technique you would apply to save time and if there is, what principle is this technique based on.