CIA officer Mary Cathison needs to drive to meet with an informant across an unwelcome city. Some roads in the city are equipped with government surveillance cameras, and Mary will be detained if cameras from more than one road observe her car on the way to her informant.
CIA officer Mary Cathison needs to drive to meet with an informant
across an unwelcome city. Some roads in the city are equipped with government surveillance cameras, and Mary will be detained if cameras from more than one road observe her car on the way to her informant.COZ Mary has a map describing the length of each road and the locations and ranges of surveillance cameras. Let n be the number of road intersections and m be the number of roads in the network. Suppose s is Mary’s start location and t is the location of the informant. Help Mary find the shortest drive to reach her informant, being seen by at most one surveillance camera along the way. (Hint: Construct a graph having two vertices (v, 0) and (v, 1) for every road intersection v within the city. Vertex (v, i) represents arriving at intersection v having already been spotted by exactly i camera(s).)
Looking for a Similar Assignment? Order now and Get 10% Discount! Use Coupon Code "Newclient"
