Minimum Cost to Reach City With Discounts

Minimum Cost to Reach City With Discounts - Problem

A series of highways connect n cities numbered from 0 to n - 1. You are given a 2D integer array highways where highways[i] = [city1_i, city2_i, toll_i] indicates that there is a highway that connects city1_i and city2_i, allowing a car to go from city1_i to city2_i and vice versa for a cost of toll_i.

You are also given an integer discounts which represents the number of discounts you have. You can use a discount to travel across the i^th highway for a cost of toll_i / 2 (integer division). Each discount may only be used once, and you can only use at most one discount per highway.

Return the minimum total cost to go from city 0 to city n - 1, or -1 if it is not possible to go from city 0 to city n - 1.

Input & Output

Example 1 — Basic Highway Network

$ Input: n = 5, highways = [[0,1,4],[1,2,3],[2,3,8],[3,4,2],[1,3,6]], discounts = 1

› Output: 8

💡 Note: Optimal path: 0→1→3→4. Use discount on highway (2,3) with toll 8, making it cost 4. Total: 4 + 6 + 2 = 12. Actually, better path: 0→1→2→3→4 = 4+3+4+2 = 13 with discount on (2,3). Best is 0→1→3→4 = 4+6+2 = 12, but with discount on (1,3): 4+3+2 = 9. Wait, let me recalculate: 0→1→3→4 costs 4+6+2=12 normally, with discount on (1,3): 4+3+2=9. Actually checking: 0→1→2→3→4 = 4+3+8+2=17, with discount on (2,3): 4+3+4+2=13. So minimum is 9 via 0→1→3→4 with discount.

Example 2 — No Path Available

$ Input: n = 4, highways = [[0,1,3],[2,3,5]], discounts = 2

› Output: -1

💡 Note: Cities 0-1 are connected, cities 2-3 are connected, but no path exists from city 0 to city 3. Return -1.

Example 3 — Single City

$ Input: n = 1, highways = [], discounts = 0

› Output: 0

💡 Note: Already at destination (city 0 = city n-1 when n=1), so cost is 0.

Constraints

1 ≤ n ≤ 1000
0 ≤ highways.length ≤ 1000
highways[i].length == 3
0 ≤ city1_i, city2_i ≤ n - 1
city1_i ≠ city2_i
0 ≤ toll_i ≤ 10⁵
0 ≤ discounts ≤ 500
There are no duplicate highways.

Visualization

Tap to expand

Understanding the Visualization

Input

Highway network with tolls and available discounts

Process

Use modified Dijkstra considering discount states

Output

Minimum cost to reach destination city

Key Takeaway

🎯 Key Insight: Use modified Dijkstra treating (city, discounts_remaining) as unique states

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to treat each (city, remaining_discounts) pair as a unique state in Dijkstra's algorithm. For each highway, we consider both using and not using a discount, ensuring we find the minimum cost path. Best approach uses Modified Dijkstra with state tracking. Time: O((V+E)*D*log(V*D)), Space: O(V*D)

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Backtracking	O(2^E)	O(n)	Try all possible paths with all discount combinations
Modified Dijkstra with State	O((V + E) * D * log(V * D))	O(V * D)	Use Dijkstra's algorithm tracking city and remaining discounts as state

DFS with Backtracking — Algorithm Steps

Step 1: Build adjacency list from highways
Step 2: Use DFS to explore all paths with remaining discounts
Step 3: For each edge, try both with and without discount
Step 4: Track minimum cost to reach destination

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin at city 0 with all discounts available

Branch Paths

For each highway, try both with and without discount

Track Minimum

Keep track of minimum cost found to destination

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_CITIES 1000
#define MAX_HIGHWAYS 10000

typedef struct {
    int neighbor;
    int toll;
} Edge;

typedef struct {
    Edge edges[MAX_HIGHWAYS];
    int count;
} AdjList;

AdjList graph[MAX_CITIES];
int visited[MAX_CITIES];

int dfs(int city, int target, int remainingDiscounts, int n) {
    if (city == target) return 0;
    
    int minCost = INT_MAX;
    
    for (int i = 0; i < graph[city].count; i++) {
        int neighbor = graph[city].edges[i].neighbor;
        int toll = graph[city].edges[i].toll;
        
        if (visited[neighbor]) continue;
        
        visited[neighbor] = 1;
        
        // Try without discount
        int cost = dfs(neighbor, target, remainingDiscounts, n);
        if (cost != INT_MAX) {
            if (toll + cost < minCost) {
                minCost = toll + cost;
            }
        }
        
        // Try with discount if available
        if (remainingDiscounts > 0) {
            cost = dfs(neighbor, target, remainingDiscounts - 1, n);
            if (cost != INT_MAX) {
                if (toll / 2 + cost < minCost) {
                    minCost = toll / 2 + cost;
                }
            }
        }
        
        visited[neighbor] = 0;
    }
    
    return minCost;
}

int solution(int n, int highways[][3], int highwayCount, int discounts) {
    if (n == 1) return 0;
    
    // Initialize graph
    for (int i = 0; i < n; i++) {
        graph[i].count = 0;
        visited[i] = 0;
    }
    
    // Build adjacency list
    for (int i = 0; i < highwayCount; i++) {
        int city1 = highways[i][0];
        int city2 = highways[i][1];
        int toll = highways[i][2];
        
        graph[city1].edges[graph[city1].count] = (Edge){city2, toll};
        graph[city1].count++;
        
        graph[city2].edges[graph[city2].count] = (Edge){city1, toll};
        graph[city2].count++;
    }
    
    visited[0] = 1;
    int result = dfs(0, n - 1, discounts, n);
    return result == INT_MAX ? -1 : result;
}

int main() {
    int n, discounts;
    scanf("%d", &n);
    
    // Parse highways array (simplified)
    int highways[MAX_HIGHWAYS][3];
    int highwayCount = 0;
    
    scanf("%d", &discounts);
    
    int result = solution(n, highways, highwayCount, discounts);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^E)

For each edge, we try 2 options (discount or not), leading to exponential combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth can go up to n cities in the worst case

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler