Skip to content

1928. Minimum Cost to Reach Destination in Time 👍

  • Time: $O(|E| + |V|\log |E|)$
  • Space: $O(|V|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
struct T {
  int node;
  int cost;
  int time;
  T(int node, int cost, int time) : node(node), cost(cost), time(time) {}
};

class Solution {
 public:
  int minCost(int maxTime, vector<vector<int>>& edges,
              vector<int>& passingFees) {
    const int n = passingFees.size();
    vector<vector<pair<int, int>>> graph(n);
    auto compare = [](const T& a, const T& b) {
      return a.cost == b.cost ? a.time > b.time : a.cost > b.cost;
    };
    priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);
    vector<int> cost(n, INT_MAX);  // cost[i] := min cost to reach cities[i]
    vector<int> time(n, INT_MAX);  // time[i] := min time to reach cities[i]

    for (const auto& e : edges) {
      const int x = e[0];
      const int y = e[1];
      const int t = e[2];
      graph[x].emplace_back(y, t);
      graph[y].emplace_back(x, t);
    }

    // start with node 0 with cost = time = 0
    minHeap.emplace(0, passingFees[0], 0);
    cost[0] = passingFees[0];
    time[0] = 0;

    while (!minHeap.empty()) {
      const auto [x, currCost, currTime] = minHeap.top();
      minHeap.pop();
      for (const auto& [y, pathTime] : graph[x]) {
        if (currTime + pathTime <= maxTime) {
          // go from x -> y
          const int newCost = currCost + passingFees[y];
          const int newTime = currTime + pathTime;
          if (cost[y] > newCost) {
            cost[y] = newCost;
            time[y] = newTime;
            minHeap.emplace(y, newCost, newTime);
          } else if (time[y] > newTime) {
            time[y] = newTime;
            minHeap.emplace(y, newCost, newTime);
          }
        }
      }
    }

    return cost.back() == INT_MAX ? -1 : cost.back();
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class T {
  public int node;
  public int cost;
  public int time;
  public T(int node, int cost, int time) {
    this.node = node;
    this.cost = cost;
    this.time = time;
  }
}

class Solution {
  public int minCost(int maxTime, int[][] edges, int[] passingFees) {
    final int n = passingFees.length;
    List<Pair<Integer, Integer>>[] graph = new List[n];
    Queue<T> minHeap =
        new PriorityQueue<>((a, b) -> a.cost == b.cost ? a.time - b.time : a.cost - b.cost);
    int[] cost = new int[n]; // cost[i] := min cost to reach cities[i]
    int[] time = new int[n]; // time[i] := min time to reach cities[i]
    Arrays.fill(cost, Integer.MAX_VALUE);
    Arrays.fill(time, Integer.MAX_VALUE);

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] e : edges) {
      final int x = e[0];
      final int y = e[1];
      final int t = e[2];
      graph[x].add(new Pair<>(y, t));
      graph[y].add(new Pair<>(x, t));
    }

    // start with node 0 with cost = time = 0
    minHeap.offer(new T(0, passingFees[0], 0));
    cost[0] = passingFees[0];
    time[0] = 0;

    while (!minHeap.isEmpty()) {
      final int x = minHeap.peek().node;
      final int currCost = minHeap.peek().cost;
      final int currTime = minHeap.poll().time;
      for (var node : graph[x]) {
        final int y = node.getKey();
        final int pathTime = node.getValue();
        if (currTime + pathTime <= maxTime) {
          // go from x -> y
          final int newCost = currCost + passingFees[y];
          final int newTime = currTime + pathTime;
          if (cost[y] > newCost) {
            cost[y] = newCost;
            time[y] = newTime;
            minHeap.offer(new T(y, newCost, newTime));
          } else if (time[y] > newTime) {
            time[y] = newTime;
            minHeap.offer(new T(y, newCost, newTime));
          }
        }
      }
    }

    return cost[n - 1] == Integer.MAX_VALUE ? -1 : cost[n - 1];
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
  def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
    n = len(passingFees)
    graph = [[] for _ in range(n)]
    minHeap = []  # (cost, time, node)
    cost = [math.inf] * n  # cost[i] := min cost to reach cities[i]
    time = [math.inf] * n  # time[i] := min cost to reach cities[i]

    for x, y, t in edges:
      graph[x].append((y, t))
      graph[y].append((x, t))

    # start with node 0 with cost = time = 0
    heapq.heappush(minHeap, (passingFees[0], 0, 0))
    cost[0] = passingFees[0]
    time[0] = 0

    while minHeap:
      currCost, currTime, x = heapq.heappop(minHeap)
      for y, pathTime in graph[x]:
        if currTime + pathTime <= maxTime:
          # go from x -> y
          newCost = currCost + passingFees[y]
          newTime = currTime + pathTime
          if cost[y] > newCost:
            cost[y] = newCost
            time[y] = newTime
            heapq.heappush(minHeap, (newCost, newTime, y))
          elif time[y] > newTime:
            time[y] = newTime
            heapq.heappush(minHeap, (newCost, newTime, y))

    return -1 if cost[-1] == math.inf else cost[-1]