Pythonですべての出荷を完了するために必要な総コストを求めるプログラム

リストのリスト ports が与えられているとします。ここで ports[i] は、港 i が接続されている港の一覧を表します。さらに別のリストのリスト shipments もあり、その各要素は [i, j] という形式のシーケンスで、「港 i から港 j への出荷依頼」を意味します。港 i から港 j へ出荷するコストは、2つの港間の最短経路の長さとして定義されます。このとき、すべての出荷を完了させるために必要な総コストを求めるのが課題です。

たとえば、入力が次のような場合を考えてみましょう。

ports = [[1, 4],[2],[3],[0, 1],[]]
shipments = [[1, 4]]

この場合、出力は 4 になります。これは、経路が 1 -> 2 -> 3 -> 0 -> 4 となり、最短距離が4ステップだからです。

解決のアプローチ

この問題は、全ノード間の最短距離を一括して求められる「ワーシャル・フロイド法(Floyd-Warshallアルゴリズム)」を使うと効率的に解けます。手順は以下の通りです。

• n := ports のサイズ(港の総数)
• dist := ports の情報から作成した隣接行列(初期状態では直接接続されているペアのみ距離1)
• j を 0 から n まで繰り返す:
  • i を 0 から n まで繰り返す:
    • k を 0 から n まで繰り返す:
      • dist[i][k] = min(dist[i][k], dist[i][j] + dist[j][k])
• すべての出荷 [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

このコードでは、まず対角成分(dist[i][i])を0に設定し、直接接続されている港同士の距離を1として隣接行列を初期化しています。その後、ワーシャル・フロイド法によってすべての港ペア間の最短距離を計算し、最後に各出荷依頼のコストを合計して返します。到達不可能なルート(INF)は合計から除外される点にも注目してください。計算量は O(n³) となるため、港の数が比較的少ない場合に適した手法です。