LeetCode 1928 - Minimum Cost to Reach Destination in Time

LeetCode Problem 1928

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Graph Theory

Solution

Problem Understanding

The problem asks us to find the minimum cost to travel from city 0 to city n-1 within a given time limit, maxTime, where the cost is defined by passing fees associated with each city visited. The country has n cities connected by bi-directional roads with varying travel times. Multiple roads may exist between the same pair of cities with different travel times, but no road connects a city to itself.

The input consists of edges, a 2D array representing roads and their travel times, and passingFees, an array where passingFees[i] is the fee for city i. The output is the minimum total passing fee to reach city n-1 in maxTime minutes or less. If no route satisfies the time constraint, the function should return -1.

Key constraints and implications:

• maxTime <= 1000 and n <= 1000 indicate that algorithms with cubic complexity (O(n³)) may be slow, but algorithms around O(n * maxTime) are feasible.
• Travel times and fees are positive integers, which prevents negative cycles.
• Multiple roads between cities mean that a simple shortest path algorithm may need to consider all edges individually.
• The goal is time-constrained cost minimization, not shortest path by time or cost alone, which differentiates this from classical Dijkstra problems.

Important edge cases:

• No path exists within maxTime.
• Multiple paths exist, some faster but more expensive, some slower but cheaper.
• Small graphs with just two cities.
• Paths where passing through more cities reduces cost despite longer time.

Approaches

Brute Force

The brute-force approach would be to explore all possible paths from city 0 to city n-1. For each path, we calculate the total time and cost. If the time exceeds maxTime, the path is discarded. At the end, we return the minimum cost among valid paths.

This approach is correct because it considers every possible route. However, it is impractical because the number of paths grows exponentially with n and the number of edges. Even with pruning, the solution would be too slow for n = 1000.

Optimal Approach

The key insight is that this is a time-constrained shortest path problem, where cost is the metric to minimize, but we cannot exceed maxTime. Standard Dijkstra can be adapted by tracking both time and cost simultaneously.

We can use a priority queue to explore cities, prioritizing states with the lowest cost so far. For each city, we maintain the minimum cost to reach that city within a given time. If a new path reaches a city faster or cheaper than previously recorded, it is added to the queue.

This approach leverages dynamic programming with Dijkstra-style exploration, ensuring we never ignore a path that might be feasible under the time constraint.

Algorithm Walkthrough

1. Graph Construction: Convert the edges list into an adjacency list where each city maps to its neighbors with associated travel times. This allows efficient neighbor lookup.
2. Initialize State: Use a priority queue (min-heap) to store tuples (currentCost, currentTime, cityIndex), starting with (passingFees[0], 0, 0).
3. DP Table: Maintain a 2D table dp[city][time] representing the minimum cost to reach city at exactly time minutes. Initialize all entries to infinity except the starting city at time 0.
4. Priority Queue Exploration: While the queue is not empty, pop the state with the lowest current cost. For each neighbor, calculate newTime = currentTime + travelTime and newCost = currentCost + passingFees[neighbor].
5. State Update: If newTime <= maxTime and newCost < dp[neighbor][newTime], update the DP table and push (newCost, newTime, neighbor) into the queue.
6. Result Extraction: After queue exhaustion, examine dp[n-1][0..maxTime] and select the minimum cost. If all entries are infinity, return -1.

Why it works: The priority queue ensures states with lower cost are explored first. The DP table prevents redundant exploration and guarantees that all feasible time-cost combinations are considered. This approach correctly identifies the minimum cost path within the time limit.

Python Solution

from typing import List
import heapq
import math

class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        n = len(passingFees)
        
        # Build graph
        graph = [[] for _ in range(n)]
        for u, v, t in edges:
            graph[u].append((v, t))
            graph[v].append((u, t))
        
        # DP table: min cost to reach city i at exactly time t
        dp = [ [math.inf] * (maxTime + 1) for _ in range(n) ]
        dp[0][0] = passingFees[0]
        
        # Priority queue: (currentCost, currentTime, city)
        pq = [(passingFees[0], 0, 0)]
        
        while pq:
            cost, time, city = heapq.heappop(pq)
            
            if city == n - 1:
                continue  # we will check DP table later
            
            for neighbor, travelTime in graph[city]:
                newTime = time + travelTime
                if newTime > maxTime:
                    continue
                
                newCost = cost + passingFees[neighbor]
                if newCost < dp[neighbor][newTime]:
                    dp[neighbor][newTime] = newCost
                    heapq.heappush(pq, (newCost, newTime, neighbor))
        
        minCost = min(dp[n-1])
        return minCost if minCost != math.inf else -1

The code constructs an adjacency list for the graph, initializes the DP table and priority queue, and iteratively explores paths. The DP table ensures we only update if a cheaper path is found within the allowed time, preventing unnecessary recomputation. Finally, it scans the last row to find the minimum valid cost.

Go Solution

package main

import (
    "container/heap"
    "math"
)

type State struct {
    cost int
    time int
    city int
}

type PriorityQueue []State

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].cost < pq[j].cost }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(State)) }
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func minCost(maxTime int, edges [][]int, passingFees []int) int {
    n := len(passingFees)
    
    graph := make([][][2]int, n)
    for _, e := range edges {
        u, v, t := e[0], e[1], e[2]
        graph[u] = append(graph[u], [2]int{v, t})
        graph[v] = append(graph[v], [2]int{u, t})
    }
    
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, maxTime+1)
        for j := 0; j <= maxTime; j++ {
            dp[i][j] = math.MaxInt32
        }
    }
    dp[0][0] = passingFees[0]
    
    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, State{passingFees[0], 0, 0})
    
    for pq.Len() > 0 {
        s := heap.Pop(pq).(State)
        if s.city == n-1 {
            continue
        }
        for _, neighbor := range graph[s.city] {
            nextCity, travelTime := neighbor[0], neighbor[1]
            newTime := s.time + travelTime
            if newTime > maxTime {
                continue
            }
            newCost := s.cost + passingFees[nextCity]
            if newCost < dp[nextCity][newTime] {
                dp[nextCity][newTime] = newCost
                heap.Push(pq, State{newCost, newTime, nextCity})
            }
        }
    }
    
    minCost := math.MaxInt32
    for _, c := range dp[n-1] {
        if c < minCost {
            minCost = c
        }
    }
    if minCost == math.MaxInt32 {
        return -1
    }
    return minCost
}

Go differences include explicit heap interface implementation and handling `