找出最低购买成本的程序
假设我们有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