The problem asks for the actual route, not the count. You need to reconstruct the path from city to city . While computing , store parent[v] = u whenever you update dp[v] from dp[u]. After computing , backtrack from city to city using the parent array.
Start at city , add it to the path, then move to parent[n], and repeat until you reach city . Reverse the path at the end.