The first step of the solution is computing ~d[a][b]~, the minimum distance from city ~a~ to city ~b~, for all pairs of cities. If there is no possible path between a pair of cities, we will use ~\infty~ as the distance. It follows that, if ~d[1][2] = \infty~ or ~d[2][1] = \infty~, then no solution exists. This part can easily be implemented using the Floyd-Warshall algorithm.

Let us denote by ~dp[a][b]~ the minimum number of cities that need to be monitored so that a path ~1 \to a \to b \to 1~ is possible, where cities ~a~ and ~b~ do not necessarily have to be distinct. Then it is possible to move from "state" ~dp[a][b]~ to ~dp[x][y]~ with the following cost:

$$\displaystyle dp[x][y] = dp[a][b]+d[b][x]+d[x][y]+d[y][a]-1$$

If we search the state space over all ~(a, b)~ pairs using Dijkstra's algorithm, we will obtain the optimal solution in ~dp[2][2]~.