파이썬에서 모든 배송을 완료하는 데 필요한 총 비용을 찾는 프로그램

<시간/>

포트라고 하는 목록 목록이 있다고 가정합니다. 여기서 포트[i]는 포트 i가 연결된 포트 목록을 나타냅니다. 또한 포트 i에서 포트 j로의 배송 요청이 있음을 나타내는 시퀀스 [i, j]의 각 목록이 있는 배송이라는 또 다른 목록 목록이 있습니다. 그리고 포트 i에서 포트 j까지 배송하는 비용은 두 포트에서 가장 짧은 경로의 길이이므로 모든 배송을 완료하는 데 필요한 총 비용을 찾아야 합니다.

따라서 입력이 포트 =[[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]]