home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมหา Cost ต่ำสุดจากกราฟถ่วงน้ำหนักใน Python

คำอธิบายโจทย์

กราฟ undirected edges = [u, v, w] cost ของ path = (จำนวน edges) × (max weight บน path) หา cost ต่ำสุดจาก 0 ถึง n-1

ตัวอย่าง

edges = [[0,2,100],[1,2,200],[1,3,100],[2,3,300]] → 600

วิธีแก้ปัญหา

BFS + Binary Search บน max weight:

  1. สร้าง adjacency list และ weight map
  2. Binary search บน max_weight ที่อนุญาต (จาก max ถึง 0)
  3. BFS หา shortest path (จำนวน edges น้อยที่สุด) ใช้ edge ที่ weight ≤ max_weight
  4. คำนวณ cost = distance × actual_max_weight_on_path
  5. ลด max_weight ลงเรื่อยๆ จน BFS ไม่เจอ path

โค้ด Python

from collections import defaultdict, deque

class Solution:
    def solve(self, edges):
        graph = defaultdict(list)
        weights = {}
        max_weight = 0
        N = 0
        for u, v, w in edges:
            graph[u].append(v)
            graph[v].append(u)
            weights[u, v] = w
            weights[v, u] = w
            N = max(N, u + 1, v + 1)
            max_weight = max(max_weight, w)
        
        def bfs(root, weight_cap):
            target = N - 1
            Q = deque([(root, 0, 0)])
            visited = [False] * N
            visited[0] = True
            while Q:
                v, d, current_weight = Q.pop()
                if v == N - 1:
                    return d, current_weight
                for w in graph[v]:
                    if visited[w]:
                        continue
                    new_weight = weights[v, w]
                    if new_weight <= weight_cap:
                        visited[w] = True
                        Q.appendleft((w, d + 1, max(current_weight, new_weight)))
            return -1, -1
        
        result = float("inf")
        while max_weight >= 0:
            d, weight = bfs(0, max_weight)
            if d >= 0:
                result = min(result, d * weight)
                max_weight = weight - 1
            else:
                break
        return result if result < float("inf") else -1

ob = Solution()
print(ob.solve([
    [0, 2, 100],
    [1, 2, 200],
    [1, 3, 100],
    [2, 3, 300]
]))

อินพุต

[[0, 2, 100], [1, 2, 200], [1, 3, 100], [2, 3, 300]]

เอาต์พุต

600