Problem: Minimum Valid Path The goal of this assessment is to use appropriate data structures and write algorithms to solve the minimum valid path problem. The problem is to find the minimum cost of a valid path between two given vertices in a weighted directed graph with some vertices marked as special that contains exactly one special vertex and also satisfy a particular condition on the weighting of adjacent edges as explained below. This problem resembles the problem of finding a path with minimum cost to travel between two places where the path includes exactly one special place. Learning outcome Critically analyse a specific topic whilst applying the underlying principles and concepts to the field of study Task: You are given a weighted directed graph some of whose vertices are marked as special vertices. A valid path in it is a path which satisfies the following conditions: 1. For any two adjacent edges x and y on the path, 0.5*weight(x) Sample Input 44 121 231 341 131 1 4 14 Sample Output Path: 1-3-4 Min. cost= 2 4 1 1 1 Explanation In the given sample, it is clear that path 1-3-4 is a valid path with cost 2. Though 1-2- 3-4 is also a valid path, but its cost is 3. So, 2 is the minimum cost of a valid path. Submission Submit your code and supporting Microsoft word or pdf document including screenshots of the code and brief narrative about the algorithm and utilized data structures to Moodle. You will be also required to demo your work in the class.