Standard disclaimer: your solution should use the algorithms…

Standard disclaimer: your solution should use the algorithms from class (DFS, BFS, Dijkstra’s, Topological Sort, Bellman-Ford, Floyd-Warshall, SCC, Kruskal’s, Prim’s, Ford-Fulkerson, Edmonds-Karp, and 2-SAT) as a black box subroutine for your algorithm. If you attempt to modify one of these algorithms you will not receive full credit, even if it is correct. Make sure to explain your algorithm in words (no pseudocode!), explain the correctness of your design, and state and analyze its running time. Faster—and correct—solutions are worth more credit. After escaping a notorious heist, the (in)famous pirate Britus fled north and eventually settled in a quiet southern town. To make a living, Britus now operates in the black market, discreetly distributing Cuban rum. In town, there are n distribution points and m roads. Each road r connects two distribution points and has a positive length given by l(r). Some roads are safe, but others are patrolled by the local police (who are aware of the presence of the famous pirate). Britus wants to draw an acyclic map that reaches all distribution points using safe roads whenever possible. While traveling on safe roads, Britus would like to take the longest ones to enjoy the scenery, however if he must travel on dangerous roads, Britus would like to take the shortest ones to avoid running into the police. Design an algorithm to help Britus draw the map (effectively making you an accomplice). Your input is an undirected, weighted graph where each node represents a distribution point, each edge represents a road, and the weights are the length l(r) of each road. You are also given a list S of safe roads, all other roads not in S are considered dangerous (this is, patrolled by the police), and Britus will use those only if necessary. You may assume that you can access the weights l(r) in constant time. Consider the graph shown above. Dashed edges are safe. Your algorithm should output AB, BD, AE, CD, and the dangerous edge AF. You can check that this collection of roads/edges is acyclic, uses the largest number of safe edges, and maximizes the sum of their lengths. When a dangerous road must be taken, the sum of their lengths are minimized. (please maximize this question if text box does not show)