Pythonですべての出荷を完了するための総コストを見つけるためのプログラム

ポートと呼ばれるリストのリストがあるとします。ここで、ports[i]はポートiが接続されているポートのリストを表します。また、出荷と呼ばれるリストの別のリストがあります。ここで、シーケンス[i、j]の各リストは、ポートiからポートjへの出荷要求があることを示します。また、ポートiからポートjに出荷するコストは、2つのポートからの最短経路の長さであるため、すべての出荷を完了するために必要な合計コストを見つける必要があります。

したがって、入力がポート=[[1、4]、[2]、[3]、[0、1]、[]]出荷=[[1、4]]のようである場合、出力は4になります。パスは1->2->3->0->4からです。

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

• n：=ポートのサイズ
• dist：=ポートリストからの隣接行列
• 0からnの範囲のjについては、
  • 0からnの範囲のiについては、
    • 0からnの範囲のkについては、
      • dist [i、k]=最小のdist[i、k]、dist [i、j] + dist [j、k]
• フォーム[i、j]のすべての貨物について、dist [i、j]が無限大でない場合は、リストdist [i、j]を作成します
• 生成されたリストの合計を返します。

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

例

class Solution:
   def solve(self, ports, shipments):
      n = len(ports)
      INF = 10 ** 10
      dist = [[INF for _ in range(n)] for _ in range(n)]
      for i in range(n):
         dist[i][i] = 0
      for i in range(n):
         for j in ports[i]:
            dist[i][j] = 1
      for j in range(n):
         for i in range(n):
            for k in range(n):
               dist[i][k] = min(dist[i][k], dist[i][j] + dist[j][k])

      return sum(dist[i][j] for i, j in shipments if dist[i][j] != INF)

ob = Solution()
ports = [[1, 4],[2],[3],[0, 1],[]]
shipments = [[1, 4]]
print(ob.solve(ports, shipments))

入力

[[1, 4],[2],[3],[0, 1],[]], [[1, 4]]

出力

4