Minimum Cost to Reach City With Discounts - Video Solutions

Problem Overview: You are given n cities connected by roads with toll costs. You start at city 0 and want to reach city n-1. A limited number of discounts can halve the toll cost of a road (integer division). The task is to compute the minimum total travel cost when you can apply these discounts strategically.

Approach 1: Exhaustive DFS / Backtracking (Exponential Time, O(2^m) time, O(n) space)

The most direct idea is to explore every possible path from the start city to the destination while deciding for each edge whether to apply a discount. For each traversal, you branch into two states: use a discount or pay the full cost. This generates a large decision tree because each road potentially doubles the number of states. While conceptually simple, the number of paths grows exponentially with the number of edges, making this impractical even for moderate graph sizes. This approach mainly helps you reason about the problem structure and why a shortest-path optimization is required.

Approach 2: Dijkstra with Discount State (Optimal) (O((n + m) log(n * k)) time, O(n * k) space)

This problem is a variation of a weighted shortest path. Standard Dijkstra works on a single distance per node, but here the cost depends on how many discounts you've already used. The key idea is to treat (city, discounts_used) as the state. Maintain a priority queue ordered by total cost. From each state, you relax edges in two ways: travel normally or apply a discount (if available) which halves the toll cost. Distances are stored in a 2D array dist[city][discounts_used]. Each state can push new states into the heap, ensuring the cheapest path is processed first. This guarantees the optimal solution because all edge costs remain non‑negative. This pattern is common in problems combining constraints with shortest path algorithms.

Approach 3: Layered Graph Transformation (O((n*k + m*k) log(n*k)) time, O(n*k) space)

Another way to view the same idea is by building a layered graph. Each layer represents how many discounts have been used so far. Node (u, d) means you're at city u after using d discounts. For every road u → v, create two transitions: one within the same layer (full price) and another to the next layer (discount applied). After constructing this expanded graph with n * (discounts + 1) nodes, run classic Dijkstra once. The structure makes the state transition explicit and mirrors techniques used in constrained graph problems and priority-queue based path searches using a heap.

Recommended for interviews: Interviewers expect the modified Dijkstra approach. It demonstrates you can extend classic shortest-path algorithms by encoding additional state. Mentioning the brute force search shows you understand the decision space, but implementing the priority queue solution with (city, discounts_used) states proves strong graph and algorithm design skills.