The problem asks for the maximum number of cities visited, not the sum of edge weights.
But you can model this as a longest path problem where every edge has weight . Define dp[u] as the maximum number of cities you can visit on a path from city to city . If dp[n] = -Infinity, there is no path. Otherwise, dp[n] is your answer. This converts the problem into standard longest path on a DAG with uniform weights.