1928. Minimum Cost to Reach Destination in Time

Problem Description

There is a country with n cities, numbered from 0 to n - 1, where all the cities are connected by bi-directional roads. The roads are represented by a 2D integer array edges, where edges[i] = [x_i, y_i, time_i] denotes a road between cities x_i and y_i that takes time_i 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. The passing fee 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.

Initially, 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 you passed through at some moment during 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

For example, let's suppose we have maxTime = 10, edges = [[0, 1, 2], [1, 2, 4], [2, 3, 2]], and passingFees = [1, 2, 3, 4]. The cities and roads can be illustrated as follows:

1
2
31
4 \
5  2---3
6 / \
70---2

We will solve the problem step-by-step with an algorithm called Dijkstra.

Solution Approach

The solution uses the Dijkstra algorithm to find the shortest path. Dijkstra helps us find the shortest path between nodes in a graph as well as the minimum total cost for passing each city. For this problem, we use Dijkstra to find the smallest time and cost to reach each city via different roads.

We will use a priority queue (min-heap) to keep track of the minimum cost and time reachable for each city. The algorithm works as follows:

1. Create a graph representing the cities and roads.
2. Initialize cost and distance arrays, and add the starting city to the priority queue.
3. While the priority queue is not empty, pop the next city with the minimum cost and time.
4. If we have reached the destination city, return the cost.
5. If not, loop through the neighboring cities and update their costs and times, adding them to the priority queue if necessary.

Let's now discuss the solution implementation.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int minCost(int maxTime, vector<vector<int>>& edges,
6              vector<int>& passingFees) {
7    const int n = passingFees.size();
8    vector<vector<pair<int, int>>> graph(n);
9
10    // Create the graph with edges
11    for (const vector<int>& edge : edges) {
12      const int u = edge[0];
13      const int v = edge[1];
14      const int w = edge[2];
15      graph[u].emplace_back(v, w);
16      graph[v].emplace_back(u, w);
17    }
18
19    // Run Dijkstra algorithm
20    return dijkstra(graph, 0, n - 1, maxTime, passingFees);
21  }
22
23 private:
24  int dijkstra(const vector<vector<pair<int, int>>>& graph, int src, int dst,
25               int maxTime, const vector<int>& passingFees) {
26    // cost[i] := min cost to reach cities[i]
27    vector<int> cost(graph.size(), INT_MAX);
28    // dist[i] := min time to reach cities[i]
29    vector<int> dist(graph.size(), maxTime + 1);
30    using T = tuple<int, int, int>;  // (cost[u], dist[u], u)
31    priority_queue<T, vector<T>, greater<>> minHeap;
32
33    cost[src] = passingFees[src];
34    dist[src] = 0;
35    minHeap.emplace(cost[src], dist[src], src);
36
37    while (!minHeap.empty()) {
38      const auto [currCost, d, u] = minHeap.top();
39      minHeap.pop();
40      if (u == dst)
41        return cost[dst];
42      for (const auto& [v, w] : graph[u]) {
43        if (d + w > maxTime)
44          continue;
45        // Go from u -> v.
46        if (currCost + passingFees[v] < cost[v]) {
47          cost[v] = currCost + passingFees[v];
48          dist[v] = d + w;
49          minHeap.emplace(cost[v], dist[v], v);
50        } else if (d + w < dist[v]) {
51          dist[v] = d + w;
52          minHeap.emplace(currCost + passingFees[v], dist[v], v);
53        }
54      }
55    }
56
57    return -1;
58  }
59};

The C++ solution follows the algorithm mentioned above. It creates a graph to represent the cities and roads, initializes the cost and distance arrays, and uses Dijkstra's algorithm to find the minimum cost with the given time constraint.## Python Solution

1
2python
3from heapq import heappop, heappush
4
5class Solution:
6    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
7        n = len(passingFees)
8        graph = {i: [] for i in range(n)}
9        
10        for u, v, w in edges:
11            graph[u].append((v, w))
12            graph[v].append((u, w))
13        
14        cost = [float('inf')] * n
15        dist = [maxTime + 1] * n
16        min_heap = [(passingFees[0], 0, 0)]
17        
18        cost[0] = passingFees[0]
19        dist[0] = 0
20        
21        while min_heap:
22            curr_cost, d, u = heappop(min_heap)
23                
24            if u == n - 1:
25                return cost[u]
26            
27            for v, w in graph[u]:
28                if d + w > maxTime:
29                    continue
30                
31                if curr_cost + passingFees[v] < cost[v]:
32                    cost[v] = curr_cost + passingFees[v]
33                    dist[v] = d + w
34                    heappush(min_heap, (cost[v], dist[v], v))
35                elif d + w < dist[v]:
36                    dist[v] = d + w
37                    heappush(min_heap, (curr_cost + passingFees[v], dist[v], v))
38        
39        return -1

The Python solution follows a similar structure as the C++ solution. Here, we use dictionaries to represent the graph and Python's heapq package to implement the priority queue (min-heap).

JavaScript Solution

1
2javascript
3class PriorityQueue {
4  constructor(compare) {
5    this.heap = [];
6    this.compare = compare;
7  }
8
9  push(val) {
10    this.heap.push(val);
11    this.heap.sort(this.compare);
12  }
13
14  pop() {
15    return this.heap.shift();
16  }
17
18  empty() {
19    return this.heap.length === 0;
20  }
21}
22
23function minCost(maxTime, edges, passingFees) {
24  const n = passingFees.length;
25  const graph = Array.from({ length: n }, () => []);
26  for (const [u, v, w] of edges) {
27    graph[u].push([v, w]);
28    graph[v].push([u, w]);
29  }
30
31  const cost = new Array(n).fill(Infinity);
32  const dist = new Array(n).fill(maxTime + 1);
33  cost[0] = passingFees[0];
34  dist[0] = 0;
35
36  const minHeap = new PriorityQueue(
37    (a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]
38  );
39  minHeap.push([cost[0], dist[0], 0]);
40
41  while (!minHeap.empty()) {
42    const [currCost, d, u] = minHeap.pop();
43    if (u === n - 1) return cost[u];
44    for (const [v, w] of graph[u]) {
45      if (d + w > maxTime) continue;
46      if (currCost + passingFees[v] < cost[v]) {
47        cost[v] = currCost + passingFees[v];
48        dist[v] = d + w;
49        minHeap.push([cost[v], dist[v], v]);
50      } else if (d + w < dist[v]) {
51        dist[v] = d + w;
52        minHeap.push([currCost + passingFees[v], dist[v], v]);
53      }
54    }
55  }
56
57  return -1;
58}

The JavaScript solution is also similar to the C++ and Python solutions. However, since JavaScript does not have a built-in heapq package, we implement a simple priority queue using arrays and comparator functions. The rest of the solution follows the same Dijkstra's algorithm steps.

All three solutions provided here correctly implement the Dijkstra algorithm for finding the minimum cost of the journey within the given time constraint, as posed in the problem statement.

Solution Implementation