Skip to content

2473. Minimum Cost to Buy Apples 👍

  • Time: $O(|E| + |V|^2\log |E|)$
  • Space: $O(|V| + |E|)$
 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
class Solution {
 public:
  vector<long long> minCost(int n, vector<vector<int>>& roads,
                            vector<int>& appleCost, int k) {
    vector<long long> ans;
    vector<vector<pair<int, long long>>> graph(n);

    for (const vector<int>& road : roads) {
      const int u = road[0] - 1;
      const int v = road[1] - 1;
      const int w = road[2];
      graph[u].emplace_back(v, w);
      graph[v].emplace_back(u, w);
    }

    for (int i = 0; i < n; ++i)
      ans.push_back(dijkstra(graph, i, appleCost, k));

    return ans;
  }

 private:
  long long dijkstra(const vector<vector<pair<int, long long>>>& graph, int i,
                     const vector<int>& appleCost, int k) {
    vector<long long> forwardCost(graph.size(), LLONG_MAX);
    vector<long long> totalCost(graph.size(), LLONG_MAX);
    forwardCost[i] = 0;
    queue<int> q{{i}};

    while (!q.empty()) {
      const int u = q.front();
      q.pop();
      for (const auto& [v, w] : graph[u]) {
        const long long nextCost = forwardCost[u] + w;
        if (nextCost >= forwardCost[v])
          continue;
        forwardCost[v] = nextCost;
        // Take apple at city v and return back to city i.
        totalCost[v] = (k + 1) * nextCost + appleCost[v];
        q.push(v);
      }
    }

    return min(static_cast<long long>(appleCost[i]),
               *min_element(begin(totalCost), end(totalCost)));
  }
};

 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
class Solution {
  public long[] minCost(int n, int[][] roads, int[] appleCost, int k) {
    long[] ans = new long[n];
    List<Pair<Integer, Integer>>[] graph = new List[n];

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

    for (int[] road : roads) {
      final int u = road[0] - 1;
      final int v = road[1] - 1;
      final int w = road[2];
      graph[u].add(new Pair<>(v, w));
      graph[v].add(new Pair<>(u, w));
    }

    for (int i = 0; i < n; ++i)
      ans[i] = dijkstra(graph, i, appleCost, k);

    return ans;
  }

  private long dijkstra(List<Pair<Integer, Integer>>[] graph, int i, int[] appleCost, int k) {
    long[] forwardCost = new long[graph.length];
    long[] totalCost = new long[graph.length];
    Arrays.fill(forwardCost, Long.MAX_VALUE);
    Arrays.fill(totalCost, Long.MAX_VALUE);
    forwardCost[i] = 0;
    Queue<Integer> q = new LinkedList<>(Arrays.asList(i));

    while (!q.isEmpty()) {
      final int u = q.poll();
      for (Pair<Integer, Integer> pair : graph[u]) {
        final int v = pair.getKey();
        final int w = pair.getValue();
        final long nextCost = forwardCost[u] + w;
        if (nextCost >= forwardCost[v])
          continue;
        forwardCost[v] = nextCost;
        // Take apple at city v and return back to city i.
        totalCost[v] = (k + 1) * nextCost + appleCost[v];
        q.offer(v);
      }
    }

    return Math.min(appleCost[i], Arrays.stream(totalCost).min().getAsLong());
  }
}

 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
class Solution:
  def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:
    graph = [[] for _ in range(n)]

    for u, v, w in roads:
      graph[u - 1].append((v - 1, w))
      graph[v - 1].append((u - 1, w))

    def dijkstra(i: int) -> int:
      forwardCost = [math.inf] * n
      totalCost = [math.inf] * n
      forwardCost[i] = 0
      q = collections.deque([i])

      while q:
        u = q.popleft()
        for v, w in graph[u]:
          nextCost = forwardCost[u] + w
          if nextCost >= forwardCost[v]:
            continue
          forwardCost[v] = nextCost
          # Take apple at city v and return back to city i.
          totalCost[v] = (k + 1) * nextCost + appleCost[v]
          q.append(v)

      return min(appleCost[i], min(totalCost))

    return [dijkstra(i) for i in range(n)]