โปรแกรมค้นหาต้นทุนรวมสำหรับการดำเนินการจัดส่งทั้งหมดใน python

สมมติว่าเรามีรายการที่เรียกว่าพอร์ต โดยที่ port[i] แทนรายการพอร์ตที่พอร์ต i เชื่อมต่ออยู่ เรายังมีรายการอื่นๆ ที่เรียกว่า การจัดส่ง ซึ่งแต่ละรายการของลำดับ [i, j] ซึ่งระบุว่ามีคำขอให้จัดส่งจากพอร์ต i ไปยังพอร์ต j และค่าใช้จ่ายในการจัดส่งสินค้าจากท่าเรือ i ไปยังพอร์ต j คือความยาวของเส้นทางที่สั้นที่สุดจากทั้งสองพอร์ต เราต้องหาต้นทุนทั้งหมดที่จำเป็นในการดำเนินการจัดส่งทั้งหมดให้เสร็จสิ้น

ดังนั้นหากอินพุตเป็นเหมือนพอร์ต =[[1, 4],[2],[3],[0, 1],[]] การจัดส่ง =[[1, 4]] ผลลัพธ์จะเป็น 4 เนื่องจากเส้นทางมาจาก 1 -> 2 -> 3 -> 0 -> 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของพอร์ต
• dist :=adjacency matrix จากรายการพอร์ต
• สำหรับ j ในช่วง 0 ถึง n ทำ
  • สำหรับ i ในช่วง 0 ถึง n ให้ทำ
    • สำหรับ k ในช่วง 0 ถึง n ทำ
      • 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