1928.规定时间内到达终点的最小花费

链接：1928.规定时间内到达终点的最小花费
难度：Hard
标签：图、数组、动态规划
简介：给你 maxTime，edges 和 passingFees ，请你返回完成旅行的最小费用，如果无法在 maxTime 分钟以内完成旅行，请你返回 -1 。

题解 1 - python

编辑时间：2024-10-03
执行用时：1579ms
内存消耗：27.52MB
编程语言：python
解法介绍：按费用进行优先队列

class Node:
    def __init__(self, idx: int, fee: int):
        self.idx = idx
        self.fee = fee
        self.next = []
    def __str__(self):
        return f'Node({self.idx}, {self.fee}, {list(map(lambda v: v[0].idx, self.next))})'
class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        n = len(passingFees)
        nodes = [Node(i, passingFees[i]) for i in range(n)]
        for start, end, time in edges:
            nodes[start].next.append((end, time))
            nodes[end].next.append((start, time))
        q = [(passingFees[0], 0, 0)]
        time_used = defaultdict(dict)
        res = inf
        while q:
            fee, time, node_idx = heappop(q)
            node = nodes[node_idx]
            if node.idx == n - 1: return fee
            for child_idx, t in node.next:
                child = nodes[child_idx]
                next_time = time + t
                next_fee = fee + child.fee
                if next_time <= maxTime and \
                    (next_time not in time_used[child_idx] or \
                     time_used[child_idx][next_time] > next_fee):
                    time_used[child_idx][next_time] = next_fee
                    heappush(q, (next_fee, next_time, child.idx))
        return -1

题解 1 - python​

题解 1 - python