Chương trình tìm chi phí tối thiểu từ đồ thị có trọng số trong Python

Cho danh sách cạnh edges = [u, v, w] biểu diễn đồ thị vô hướng n đỉnh 0..n-1. Chi phí đường đi = (số cạnh) * (trọng số lớn nhất trên đường đi). Tìm chi phí tối thiểu từ 0 đến n-1, hoặc -1 nếu không có đường.

Ví dụ: edges = [[0,2,100],[1,2,200],[1,3,100],[2,3,300]] → 600.

Giải pháp

BFS lặp với ngưỡng trọng số giảm dần:

• Xây dựng đồ thị, tìm max_weight
• Lặp weight_cap từ max_weight xuống 0:
  • BFS từ 0 chỉ dùng cạnh weight <= weight_cap
  • Nếu đến được n-1: cập nhật result = min(result, d * weight), weight_cap = weight - 1
  • Ngược lại: break
• BFS ưu tiên độ dài đường ngắn nhất, theo dõi max_weight trên đường

Ví dụ minh họa

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]
]))

Đầu vào

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

Đầu ra

600