Skip to content

2662. Minimum Cost of a Path With Special Roads 👍

  • Time: $O(n^2\log n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  int minimumCost(vector<int>& start, vector<int>& target,
                  vector<vector<int>>& specialRoads) {
    return dijkstra(specialRoads, start[0], start[1], target[0], target[1]);
  }

 private:
  int dijkstra(const vector<vector<int>>& specialRoads, int srcX, int srcY,
               int dstX, int dstY) {
    const int n = specialRoads.size();
    // dist[i] := the minimum distance of (srcX, srcY) to
    // specialRoads[i](x2, y2)
    vector<int> dist(specialRoads.size(), INT_MAX);
    using P = pair<int, int>;  // (d, u), where u := the i-th specialRoads
    priority_queue<P, vector<P>, greater<>> minHeap;

    // (srcX, srcY) -> (x1, y1) to cost -> (x2, y2)
    for (int u = 0; u < n; ++u) {
      const int x1 = specialRoads[u][0];
      const int y1 = specialRoads[u][1];
      const int cost = specialRoads[u][4];
      const int d = abs(x1 - srcX) + abs(y1 - srcY) + cost;
      dist[u] = d;
      minHeap.emplace(dist[u], u);
    }

    while (!minHeap.empty()) {
      const auto [d, u] = minHeap.top();
      minHeap.pop();
      if (d > dist[u])
        continue;
      const int ux2 = specialRoads[u][2];
      const int uy2 = specialRoads[u][3];
      for (int v = 0; v < n; ++v) {
        if (v == u)
          continue;
        const int vx1 = specialRoads[v][0];
        const int vy1 = specialRoads[v][1];
        const int vcost = specialRoads[v][4];
        // (ux2, uy2) -> (vx1, vy1) to vcost -> (vx2, vy2)
        const int newDist = d + abs(vx1 - ux2) + abs(vy1 - uy2) + vcost;
        if (newDist < dist[v]) {
          dist[v] = newDist;
          minHeap.emplace(dist[v], v);
        }
      }
    }

    int ans = abs(dstX - srcX) + abs(dstY - srcY);
    for (int u = 0; u < n; ++u) {
      const int x2 = specialRoads[u][2];
      const int y2 = specialRoads[u][3];
      // (srcX, srcY) -> (x2, y2) -> (dstX, dstY).
      ans = min(ans, dist[u] + abs(dstX - x2) + abs(dstY - y2));
    }
    return ans;
  }
};

 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
class Solution {
  public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
    return dijkstra(specialRoads, start[0], start[1], target[0], target[1]);
  }

  private int dijkstra(int[][] specialRoads, int srcX, int srcY, int dstX, int dstY) {
    final int n = specialRoads.length;
    // dist[i] := the minimum distance of (srcX, srcY) to
    // specialRoads[i](x2, y2)
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    // (d, u), where u := the i-th specialRoads
    Queue<Pair<Integer, Integer>> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey));

    // (srcX, srcY) -> (x1, y1) to cost -> (x2, y2)
    for (int u = 0; u < n; ++u) {
      final int x1 = specialRoads[u][0];
      final int y1 = specialRoads[u][1];
      final int cost = specialRoads[u][4];
      final int d = Math.abs(x1 - srcX) + Math.abs(y1 - srcY) + cost;
      dist[u] = d;
      minHeap.offer(new Pair<>(dist[u], u));
    }

    while (!minHeap.isEmpty()) {
      final int d = minHeap.peek().getKey();
      final int u = minHeap.poll().getValue();
      if (d > dist[u])
        continue;
      final int ux2 = specialRoads[u][2];
      final int uy2 = specialRoads[u][3];
      for (int v = 0; v < n; ++v) {
        if (v == u)
          continue;
        final int vx1 = specialRoads[v][0];
        final int vy1 = specialRoads[v][1];
        final int vcost = specialRoads[v][4];
        // (ux2, uy2) -> (vx1, vy1) to vcost -> (vx2, vy2)
        final int newDist = d + Math.abs(vx1 - ux2) + Math.abs(vy1 - uy2) + vcost;
        if (newDist < dist[v]) {
          dist[v] = newDist;
          minHeap.offer(new Pair<>(dist[v], v));
        }
      }
    }

    int ans = Math.abs(dstX - srcX) + Math.abs(dstY - srcY);
    for (int u = 0; u < n; ++u) {
      final int x2 = specialRoads[u][2];
      final int y2 = specialRoads[u][3];
      // (srcX, srcY) -> (x2, y2) -> (dstX, dstY).
      ans = Math.min(ans, dist[u] + Math.abs(dstX - x2) + Math.abs(dstY - y2));
    }
    return ans;
  }
}

 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
class Solution:
  def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
    return self.dijkstra(specialRoads, *start, *target)

  def dijkstra(self, specialRoads: List[List[int]], srcX: int, srcY: int, dstX: int, dstY: int) -> int:
    n = len(specialRoads)
    # dist[i] := the minimum distance of (srcX, srcY) to specialRoads[i](x2, y2)
    dist = [math.inf] * n
    minHeap = []  # (d, u),(d, u), where u := the i-th specialRoads

    # (srcX, srcY) -> (x1, y1) to cost -> (x2, y2)
    for u, (x1, y1, _, _, cost) in enumerate(specialRoads):
      d = abs(x1 - srcX) + abs(y1 - srcY) + cost
      dist[u] = d
      heapq.heappush(minHeap, (dist[u], u))

    while minHeap:
      d, u = heapq.heappop(minHeap)
      if d > dist[u]:
        continue
      _, _, ux2, uy2, _ = specialRoads[u]
      for v in range(n):
        if v == u:
          continue
        vx1, vy1, _, _, vcost = specialRoads[v]
        # (ux2, uy2) -> (vx1, vy1) to vcost -> (vx2, vy2)
        newDist = d + abs(vx1 - ux2) + abs(vy1 - uy2) + vcost
        if newDist < dist[v]:
          dist[v] = newDist
          heapq.heappush(minHeap, (dist[v], v))

    ans = abs(dstX - srcX) + abs(dstY - srcY)
    for u in range(n):
      _, _, x2, y2, _ = specialRoads[u]
      # (srcX, srcY) -> (x2, y2) -> (dstX, dstY).
      ans = min(ans, dist[u] + abs(dstX - x2) + abs(dstY - y2))

    return ans