We are given a weighted graph G = (V, E) with weights given by W. The nodes represent cities and the edges are (positive) distances between the cities. We want to get a car that can travel between any two cities: it can leave with a full tank of gas, but cannot purchase gas until it reached its destination. The zero-stop capacity of the car we purchase is defined to be the longest distance between any two cities that we may travel (but of course, between any two cities we would take the shortest path). A simple way to compute this is to run Floyd-Warshall, and then look at all pairs of vertices/cities and return the greatest distance. Formally, Floyd-Warshall returns W, where W[u, v] is the length of the shortest route from city u to v. The zero-stop capacity is thus

max{ W[u, v] | u, v V }.

Now suppose that you want to calculate the necessary one-stop capacity of a potential car: we are allowed to stop at just one intermediate city to purchase gas for the car. Please determine what capacity would be needed for our car to travel between any two cities with at most one refueling stop. For this problem, just provide the mathematical representation(s) (and you can refer to the above example of the zero-stop capacity); do not write codes or pseudocodes, and writing codes or pseudocodes will not receive any credits. [5 points]

Note that the first two steps of the development of a dynamic programming algorithm for a problem are as follows: (1) describe the structure of the subproblem; (2) find a recurrence for the optimal value of the subproblem in terms of smaller subproblems. For the two problems below, perform these two steps. Do not write codes or pseudocodesjust the subproblem and recurrence structure, including initial conditions when needed; writing codes or pseudocodes will not receive any credits.