Consider an extended version of the Shortest-Path problem. Suppose that you want to

traverse from city s to city t. In addition, for some reason, you also need to pass through cities x,

y, and z (in any order) during your trip. Your objective is to minimize the cost of the trip. The

problem can be formulated as a graph problem as follows: Given a positively weighted directed

graph G and ve vertices s, t, x, y, z, find a path from s to t that contains the vertices x, y,

z such that the path is the shortest over all paths from s to t that contain x, y, z, assuming

that these paths are allowed to contain repeated vertices and edges. Develop an O(mlog n)-time

algorithm for this problem.