Reconstructing the Route

The problem asks for the actual route, not the count. You need to reconstruct the path from city $1$ to city $n$. While computing $dp$, store parent[v] = u whenever you update dp[v] from dp[u]. After computing $dp$, backtrack from city $n$ to city $1$ using the parent array.

Start at city $n$, add it to the path, then move to parent[n], and repeat until you reach city $1$. Reverse the path at the end.