Chương trình tìm chi phí tối thiểu để mua tất cả vật phẩm trong Python

Có N vật phẩm 0..N-1. Mua set i với giá sets[i][2] nhận vật phẩm từ sets[i][0] đến sets[i][1]. Có thể bỏ vật phẩm i với chi phí removals[i]. Tìm chi phí tối thiểu để có đúng 1 mỗi vật phẩm 0..N-1, hoặc -1 nếu không thể.

Ví dụ: sets=[[0,4,4],[0,5,12],[2,6,9],[4,8,10]], removals=[2,5,4,6,8] → 4.

Giải pháp

Mô hình hóa thành bài toán đường đi ngắn nhất trên đồ thị:

• Đỉnh 0..N: trạng thái đã có vật phẩm 0..i-1
• Cạnh s -> e+1 với trọng số w: mua set [s,e] giá w
• Cạnh i+1 -> i với trọng số removals[i]: bỏ vật phẩm i
• Dijkstra từ 0 đến N

Ví dụ minh họa

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]))

Đầu vào

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

Đầu ra

4