Pythonですべてを購入するための最小コストを見つけるためのプログラム

0、1、2、…、N-1とマークされたN個のアイテムがあるとします。次に、セットと呼ばれるサイズSの2Dリストが与えられます。ここでは、価格セット[i、2]のi番目のセットを購入でき、セット[i、0]からセット[i、1]までのすべてのアイテムを受け取ります。また、削除と呼ばれるサイズNのリストがあり、価格の削除のためにi番目の要素の1つのインスタンスを破棄できます[i]。したがって、0からN-1までのすべての要素の1つを正確に購入するための最小コストを見つける必要があります。これができない場合、結果は-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になります。

これを解決するには、次の手順に従います-

• N：=削除のサイズ

• グラフ：=サイズ（N + 1）x（N + 1）の新しい行列

• セット内の各s、e、wについて、実行します

  • グラフに[e+1、w]を追加します[s]

• インデックスiの各i、r、および削除のアイテムrについて、実行します

  • グラフに[i、r]を追加[i + 1]

• pq：=新しいヒープ

• dist：=新しい地図

• dist [0]：=0

• pqが空でない間、実行します

  • d、e：=ヒープpqから最小のアイテムを削除します

  • dist [e]

    • 次の反復を続行します

  • eがNと同じ場合、

    • dを返す

  • 各neiについて、グラフ[e]のwは、実行します

    • d2：=d + w

    • d2

      • dist [nei]：=d2

      • [d2、nei]をpqに追加

• -1を返す

例

理解を深めるために、次の実装を見てみましょう-

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