# Minimum Cost to Reach Destination in Time
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-to-reach-destination-in-time)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-reach-destination-in-time
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Graph
---
## Problem
There is a country of `n` cities numbered from `0` to `n - 1` where **all the cities are connected** by bi-directional roads. The roads are represented as a 2D integer array `edges` where `edges[i] = [xi, yi, timei]` denotes a road between cities `xi` and `yi` that takes `timei` minutes to travel. There may be multiple roads of differing travel times connecting the same two cities, but no road connects a city to itself.

Each time you pass through a city, you must pay a passing fee. This is represented as a **0-indexed** integer array `passingFees` of length `n` where `passingFees[j]` is the amount of dollars you must pay when you pass through city `j`.

In the beginning, you are at city `0` and want to reach city `n - 1` in `maxTime` **minutes or less**. The **cost** of your journey is the **summation of passing fees** for each city that you passed through at some moment of your journey (**including** the source and destination cities).

Given `maxTime`, `edges`, and `passingFees`, return _the **minimum cost** to complete your journey, or_ `-1` _if you cannot complete it within_ `maxTime` _minutes_.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-cost-to-reach-destination-in-time/image0.png)

**Input:** maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
**Output:** 11
**Explanation:** The path to take is 0 -> 1 -> 2 -> 5, which takes 30 minutes and has $11 worth of passing fees.

**Example 2:**

**![](https://assets.glich.co/dsa/minimum-cost-to-reach-destination-in-time/image1.png)**

**Input:** maxTime = 29, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
**Output:** 48
**Explanation:** The path to take is 0 -> 3 -> 4 -> 5, which takes 26 minutes and has $48 worth of passing fees.
You cannot take path 0 -> 1 -> 2 -> 5 since it would take too long.

**Example 3:**

**Input:** maxTime = 25, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
**Output:** -1
**Explanation:** There is no way to reach city 5 from city 0 within 25 minutes.

**Constraints:**

* `1 <= maxTime <= 1000`
* `n == passingFees.length`
* `2 <= n <= 1000`
* `n - 1 <= edges.length <= 1000`
* `0 <= xi, yi <= n - 1`
* `1 <= timei <= 1000`
* `1 <= passingFees[j] <= 1000`
* The graph may contain multiple edges between two nodes.
* The graph does not contain self loops.

# Approaches
## Modified Dijkstra's Algorithm
This problem can be modeled as a shortest path problem on a graph with a twist: we have two metrics to consider, time and cost. We want to minimize cost, subject to a time constraint. A standard Dijkstra's algorithm, which minimizes a single weight, is not directly applicable. This approach adapts Dijkstra's algorithm by modifying the state and pruning strategy to handle both metrics.
**Time:** O(m * maxTime * log(n * maxTime)), where `n` is the number of cities, `m` is the number of edges. In the worst case, the number of states in the priority queue can be proportional to `n * maxTime`, leading to this complexity. · **Space:** O(n * maxTime), for storing states in the priority queue in the worst case.
**Pros:** Conceptually builds upon the well-known Dijkstra's algorithm.; Can be more intuitive for those very familiar with graph traversal algorithms.
**Cons:** Less efficient than the dynamic programming approach due to the overhead of the priority queue and potentially exploring a large number of states.; The pruning logic is complex to get right. A simple pruning strategy might discard optimal solutions, while a lenient one leads to poor performance.; Worst-case time and space complexity are higher than the DP solution.
### Explanation
We can use a priority queue that prioritizes states with the minimum travel time. Each state in the priority queue will be a tuple of `(time, cost, city)`. To optimize the search and avoid exploring suboptimal paths, we maintain an array, `minCost`, where `minCost[i]` stores the minimum cost found so far to reach city `i` within the `maxTime` limit.

The algorithm proceeds as follows:
1.  Initialize a `minCost` array for all cities to infinity, except for the start city `0`, whose cost is its passing fee.
2.  Push the starting state `(0, passingFees[0], 0)` into a priority queue ordered by time.
3.  Repeatedly extract the state with the smallest time `(t, c, u)` from the queue.
4.  If the cost `c` to reach city `u` is already greater than or equal to the minimum cost found so far for `u` (`minCost[u]`), we can prune this path. This is because we process states in increasing order of time, so any previously processed path to `u` was faster and had a cost no more than `c`. Thus, the current path is dominated and can't lead to a better overall solution.
5.  If the path isn't pruned, we explore the neighbors `v` of city `u`. For each neighbor, we calculate the new time and cost. If the new path is valid (i.e., `newTime <= maxTime`) and offers a cheaper way to reach `v` (`newCost < minCost[v]`), we update `minCost[v]` and push the new state `(newTime, newCost, v)` into the priority queue.
6.  The algorithm continues until the priority queue is empty. The final answer is `minCost[n-1]`, which will hold the minimum cost to reach the destination city. If `minCost[n-1]` remains infinity, the destination is unreachable within `maxTime`.

```java
class Solution {
    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.length;
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(new int[]{edge[1], edge[2]});
            adj[edge[1]].add(new int[]{edge[0], edge[2]});
        }

        int[] minTime = new int[n];
        Arrays.fill(minTime, Integer.MAX_VALUE);
        minTime[0] = 0;

        // PQ stores {cost, time, city}, prioritized by cost
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{passingFees[0], 0, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int cost = current[0];
            int time = current[1];
            int city = current[2];

            if (time > maxTime) {
                continue;
            }

            if (city == n - 1) {
                return cost;
            }

            for (int[] neighbor : adj[city]) {
                int nextCity = neighbor[0];
                int travelTime = neighbor[1];
                int newTime = time + travelTime;
                int newCost = cost + passingFees[nextCity];

                if (newTime < minTime[nextCity]) {
                    minTime[nextCity] = newTime;
                    pq.offer(new int[]{newCost, newTime, nextCity});
                } else if (newCost < getCostForCity(pq, nextCity, newTime)) { // This is pseudo-code, real check is complex
                    // A path that is slower but cheaper needs to be considered.
                    // This is why we need to allow multiple paths to a node in the PQ.
                    // The simple minTime array is not enough for pruning.
                    // We need to track min cost for each time at each node.
                    // This leads to the DP solution being superior.
                    // A correct Dijkstra would not prune aggressively.
                    pq.offer(new int[]{newCost, newTime, nextCity});
                }
            }
        }
        return -1;
    }
    // Helper to illustrate complexity
    private int getCostForCity(PriorityQueue<int[]> pq, int city, int time) { return Integer.MAX_VALUE; }
}
```
### Algorithm
*   Create an adjacency list representation of the graph.
*   Use a priority queue to store tuples of `(cost, time, city)`. The priority queue should be ordered by `cost` to explore cheaper paths first.
*   Maintain an array `minTime` of size `n`, initialized to infinity, to store the minimum time to reach each city. Set `minTime[0] = 0`.
*   Push the starting state `(passingFees[0], 0, 0)` into the priority queue.
*   While the priority queue is not empty, extract the state with the minimum cost `(c, t, u)`.
*   If the destination `n-1` is reached, return its cost `c`. Since we prioritize by cost, the first time we extract the destination, we have found the minimum cost path.
*   If the current time `t` exceeds `maxTime`, skip this state.
*   For each neighbor `v` of `u`, calculate the `newTime` and `newCost`.
*   If the `newTime` to reach `v` is better than any time seen before (`newTime < minTime[v]`), it's a promising path. Update `minTime[v] = newTime` and push `(newCost, newTime, v)` to the queue.
*   A key insight is that a path might be slower but cheaper. The simple `minTime` check is insufficient. A correct implementation must allow exploring paths that are slower but cheaper. This means we might push multiple entries for the same city into the queue. The check `newTime < minTime[v]` helps prune some paths, but not all suboptimal ones. This complexity is why the DP approach is more efficient.
*   If the queue becomes empty and the destination has not been reached, it's impossible to get there within `maxTime`.

## Dynamic Programming
A more efficient way to solve this problem is by using dynamic programming. We can build a solution by iterating through time. The state of our DP can be defined as `dp[t][u]`, representing the minimum cost to reach city `u` at exactly time `t`.
**Time:** O(maxTime * m), where `n` is the number of cities and `m` is the number of edges. We iterate `maxTime` times, and in each iteration, we effectively iterate over all edges in the worst case. · **Space:** O(maxTime * n) to store the DP table.
**Pros:** More efficient than the Dijkstra-based approach, as it avoids the logarithmic factor from the priority queue.; The logic is straightforward and directly models the problem's state transitions over time.; Guaranteed to be correct and handles all cases systematically.
**Cons:** Requires significant memory, `O(maxTime * n)`, which might be an issue if `maxTime` or `n` were much larger.; The time complexity is directly proportional to `maxTime`, so it could be slow for very large time limits.
### Explanation
This approach avoids the complexity of a priority queue and complex pruning logic by systematically building up the solution. 

We define a 2D array `dp[maxTime + 1][n]`, where `dp[t][u]` stores the minimum cost to arrive at city `u` at exactly time `t`. This table is initialized with a value representing infinity.

The base case is the starting city at time 0: `dp[0][0] = passingFees[0]`.

We then iterate through time `t` from 0 up to `maxTime`. For each time `t`, we check every city `u`. If we have a known path to city `u` at time `t` (i.e., `dp[t][u]` is not infinity), we can extend this path to all of `u`'s neighbors. For each neighbor `v` connected by an edge with travel time `edgeTime`, the arrival time at `v` will be `t + edgeTime`. If this new time is within `maxTime`, we can potentially update the minimum cost to reach `v` at that new time:

`dp[t + edgeTime][v] = min(dp[t + edgeTime][v], dp[t][u] + passingFees[v])`

This process is repeated for all cities and all times up to `maxTime`. After the DP table is fully populated, the minimum cost to reach the destination city `n-1` is the minimum value among `dp[t][n-1]` for all `t` from 0 to `maxTime`.

If the minimum cost found for the destination remains infinity, it means it's impossible to reach within the given `maxTime`.

```java
class Solution {
    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.length;
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(new int[]{edge[1], edge[2]});
            adj[edge[1]].add(new int[]{edge[0], edge[2]});
        }

        int[][] dp = new int[maxTime + 1][n];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[0][0] = passingFees[0];

        for (int t = 0; t <= maxTime; t++) {
            for (int u = 0; u < n; u++) {
                if (dp[t][u] == Integer.MAX_VALUE) {
                    continue;
                }

                for (int[] neighbor : adj[u]) {
                    int v = neighbor[0];
                    int time = neighbor[1];
                    int newTime = t + time;

                    if (newTime <= maxTime) {
                        dp[newTime][v] = Math.min(dp[newTime][v], dp[t][u] + passingFees[v]);
                    }
                }
            }
        }

        int minCost = Integer.MAX_VALUE;
        for (int t = 0; t <= maxTime; t++) {
            minCost = Math.min(minCost, dp[t][n - 1]);
        }

        return minCost == Integer.MAX_VALUE ? -1 : minCost;
    }
}
```
### Algorithm
*   Create an adjacency list representation of the graph from the `edges` array.
*   Initialize a 2D DP table `dp[maxTime + 1][n]` with infinity. `dp[t][u]` will store the minimum cost to reach city `u` at time `t`.
*   Set the base case: `dp[0][0] = passingFees[0]`.
*   Iterate through time `t` from 0 to `maxTime`.
*   Inside this loop, iterate through each city `u` from 0 to `n-1`.
*   If `dp[t][u]` is not infinity, it means city `u` is reachable at time `t`. For each neighbor `v` of `u`:
    *   Calculate the arrival time at the neighbor: `newTime = t + travelTime`.
    *   If `newTime` is within `maxTime`, update the cost for the neighbor: `dp[newTime][v] = min(dp[newTime][v], dp[t][u] + passingFees[v])`.
*   After the loops complete, find the minimum value in the last column of the DP table corresponding to the destination city, i.e., `min(dp[t][n-1])` for all `t <= maxTime`.
*   If this minimum value is still infinity, return -1. Otherwise, return the calculated minimum cost.

# Solutions
### Java

```java
class Solution {
public
  int minCost(int maxTime, int[][] edges, int[] passingFees) {
    int n = passingFees.length;
    int[][] times = new int[n][n];
    for (int i = 0; i < n; i++)
      Arrays.fill(times[i], Integer.MAX_VALUE);
    for (int[] edge : edges) {
      int x = edge[0], y = edge[1], time = edge[2];
      if (x > y) {
        int temp = x;
        x = y;
        y = temp;
      }
      if (time <= maxTime && time < times[x][y]) {
        times[x][y] = time;
        times[y][x] = time;
      }
    }
    Map<Integer, Integer>[] map = new Map[n];
    for (int i = 0; i < n; i++)
      map[i] = new HashMap<Integer, Integer>();
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        if (times[i][j] != Integer.MAX_VALUE) {
          map[i].put(j, times[i][j]);
          map[j].put(i, times[i][j]);
        }
      }
    }
    int[][] costs = new int[n][maxTime + 1];
    for (int i = 0; i < n; i++)
      Arrays.fill(costs[i], Integer.MAX_VALUE);
    costs[0][0] = passingFees[0]; PriorityQueue < int []> priorityQueue = new PriorityQueue < int []>( new Comparator < int []>() { public int compare ( int [] indexTimeCost1 , int [] indexTimeCost2 ) { if ( indexTimeCost1 [ 2 ] != indexTimeCost2 [ 2 ]) return indexTimeCost1 [ 2 ] - indexTimeCost2 [ 2 ]; else return indexTimeCost1 [ 1 ] - indexTimeCost2 [ 1 ];
  } });
priorityQueue.offer(new int[]{0, 0, passingFees[0]});
while (!priorityQueue.isEmpty()) {
  int[] indexTimeCost = priorityQueue.poll();
  int index = indexTimeCost[0], time = indexTimeCost[1],
      cost = indexTimeCost[2];
  Map<Integer, Integer> nextMap = map[index];
  for (Map.Entry<Integer, Integer> entry : nextMap.entrySet()) {
    int nextIndex = entry.getKey(), nextTime = entry.getValue();
    int totalTime = time + nextTime;
    if (totalTime <= maxTime) {
      int totalCost = cost + passingFees[nextIndex];
      if (totalCost < costs[nextIndex][totalTime]) {
        costs[nextIndex][totalTime] = totalCost;
        priorityQueue.offer(new int[]{nextIndex, totalTime, totalCost});
      }
    }
  }
}
int minCost = Integer.MAX_VALUE;
for (int i = 0; i <= maxTime; i++)
  minCost = Math.min(minCost, costs[n - 1][i]);
return minCost == Integer.MAX_VALUE ? -1 : minCost;
}
}

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/minimum-cost-to-reach-destination-in-time/ // Time: O(ElogE) // Space: O(V + E) class Solution { typedef array < int , 3 > Node ; // node, time, cost public: int minCost ( int maxTime , vector < vector < int >>& E , vector < int >& F ) { int N = F . size (); vector < unordered_map < int , int >> G ( N ); vector < int > minTime ( N , maxTime + 1 ); for ( auto & e : E ) { int u = e [ 0 ], v = e [ 1 ], t = e [ 2 ]; if ( G [ u ]. count ( v )) { // For duplicated edges, we just need to keep track of the edge with smallest time. G [ u ][ v ] = G [ v ][ u ] = min ( G [ u ][ v ], t ); } else { G [ u ][ v ] = G [ v ][ u ] = t ; } } auto cmp = []( auto & a , auto & b ) { return a [ 2 ] > b [ 2 ]; }; // min-heap: Heap top is the node with the smallest cost to reach priority_queue < Node , vector < Node > , decltype ( cmp ) > pq ( cmp ); pq . push ({ 0 , 0 , F [ 0 ]}); minTime [ 0 ] = 0 ; while ( pq . size ()) { auto [ u , time , c ] = pq . top (); pq . pop (); if ( u == N - 1 ) return c ; for ( auto & [ v , t ] : G [ u ]) { int nt = time + t , nc = c + F [ v ]; if ( nt < minTime [ v ]) { minTime [ v ] = nt ; pq . push ({ v , nt , nc }); } } } return - 1 ; } };
```

### Python

```python
class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int: m, n = maxTime, len(passingFees) f = [[inf] * n for _ in range(m + 1)] f[0][0] = passingFees[0] for i in range(1, m + 1): for x, y, t in edges: if t <= i: f[i][x] = min(f[i][x], f[i - t][y] + passingFees[x]) f[i][y] = min(f[i][y], f[i - t][x] + passingFees[y]) ans = min(f[i][n - 1] for i in range(m + 1)) return ans if ans < inf else - 1

```