找出最低购买成本的程序

假设我们有N个项目，分别标记为0、1、2，...，N-1。然后，我们得到大小为S的二维列表，称为集合。在这里，我们可以购买价格集合[i，2]的第i个集合，并且接收集合[i，0]与集合[i，1]之间的每个项目。另外，我们有一个大小为N的列表，称为移除，在这里我们可以丢弃第i个元素的1实例进行价格移除[i]。因此，我们必须找出购买0到N-1（含0）之间的每个元素中的一个的最低成本，否则，结果是-1。

So, if the input is like sets = [
   [0, 4, 4],
   [0, 5, 12],
   [2, 6, 9],
   [4, 8, 10]
]

清除= [2、5、4、6、8]，则输出为4。

在线示例

让我们看下面的实现以更好地理解-

import heapq
from collections import defaultdict
class Solution:
   def solve(self, sets, removals):
      N = len(removals)
      graph = [[] for _ in range(N + 1)]
      for s, e, w in sets:
         graph[s].append([e + 1, w])
      for i, r in enumerate(removals):
         graph[i + 1].append([i, r])
      pq = [[0, 0]]
      dist = defaultdict(lambda: float("inf"))
      dist[0] = 0
      while pq:
         d, e = heapq.heappop(pq)
         if dist[e] < d:
            continue
         if e == N:
            return d
         for nei, w in graph[e]:
            d2 = d + w
            if d2 < dist[nei]:
               dist[nei] = d2
               heapq.heappush(pq, [d2, nei])
      return -1

ob = Solution()
print (ob.solve([
   [0, 4, 4],
   [0, 5, 12],
   [2, 6, 9],
   [4, 8, 10]
], [2, 5, 4, 6, 8]))

输入值

[[0, 4, 4],
[0, 5, 12],
[2, 6, 9],
[4, 8, 10]], [2, 5, 4, 6, 8]

4