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

难度: Hard

一个国家有 n 个城市，城市编号为 0 到 n - 1 ，题目保证 所有城市 都由双向道路 连接在一起 。道路由二维整数数组 edges 表示，其中 edges[i] = [x_i, y_i, time_i] 表示城市 x_i 和 y_i 之间有一条双向道路，耗费时间为 time_i 分钟。两个城市之间可能会有多条耗费时间不同的道路，但是不会有道路两头连接着同一座城市。

每次经过一个城市时，你需要付通行费。通行费用一个长度为 n 且下标从 0 开始的整数数组 passingFees 表示，其中 passingFees[j] 是你经过城市 j 需要支付的费用。

一开始，你在城市 0 ，你想要在 maxTime 分钟以内 （包含 maxTime 分钟）到达城市 n - 1 。旅行的费用为你经过的所有城市 通行费之和 （包括起点和终点城市的通行费）。

给你 maxTime，edges 和 passingFees ，请你返回完成旅行的 最小费用 ，如果无法在 maxTime 分钟以内完成旅行，请你返回 -1 。

示例 1：

输入：maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
输出：11
解释：最优路径为 0 -> 1 -> 2 -> 5 ，总共需要耗费 30 分钟，需要支付 11 的通行费。

示例 2：

输入：maxTime = 29, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
输出：48
解释：最优路径为 0 -> 3 -> 4 -> 5 ，总共需要耗费 26 分钟，需要支付 48 的通行费。
你不能选择路径 0 -> 1 -> 2 -> 5 ，因为这条路径耗费的时间太长。

示例 3：

输入：maxTime = 25, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
输出：-1
解释：无法在 25 分钟以内从城市 0 到达城市 5 。

提示：

1 <= maxTime <= 1000
n == passingFees.length
2 <= n <= 1000
n - 1 <= edges.length <= 1000
0 <= x_i, y_i <= n - 1
1 <= time_i <= 1000
1 <= passingFees[j] <= 1000
图中两个节点之间可能有多条路径。
图中不含有自环。

Submission

运行时间: 108 ms

内存: 16.9 MB

class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        n = len(passingFees)
        graph = [[] for _ in range(n)]
        for edge in edges:
            from_ = edge[0]
            to_ = edge[1]
            time = edge[2]
            graph[from_].append([to_, time])
            graph[to_].append([from_,time])

        # 计算以 src 为起点在 maxtime 时间内到达 dst 的最短路径
        return dijkstra(graph, 0, maxTime, n-1, passingFees)


class State:
    # 图节点的 id
    def __init__(self, id_: int, costFromSrc: int, timeFromSrc: int):
        self.id = id_
        self.costFromSrc = costFromSrc
        self.timeFromSrc = timeFromSrc

    def __lt__(self, other):
        return self.costFromSrc < other.costFromSrc


# 输入一个起点 src，计算从 src 到其他节点的最短距离
def dijkstra(graph: List[List[int]], src: int, maxtime: int, dst: int,price) -> int:
    # 定义：从起点 src 到达节点 i 的最小权重路径至少花的时间
    distTo = [float("inf") for _ in range(len(graph))]
    # 定义：从起点 src 到达节点 i 的最少通行费
    nodeNumTo = [float("inf") for _ in range(len(graph))]
    # base case
    distTo[src] = 0
    nodeNumTo[src] = price[src]

    # 优先级队列，costFromSrc 较小的排在前面
    pq = []
    # 从起点 src 开始进行 BFS
    heapq.heappush(pq, State(src, price[0], 0))

    while pq:
        curState = heapq.heappop(pq)
        curNodeID = curState.id
        costFromSrc = curState.costFromSrc
        timeFromSrc = curState.timeFromSrc

        if costFromSrc >nodeNumTo[curNodeID] and timeFromSrc > distTo[curNodeID]:
            continue

        if timeFromSrc > maxtime:
            # 时间耗尽
            continue

        if curNodeID == dst:
            # 找到最短路径
            return costFromSrc


        # 将 curNode 的相邻节点装入队列
        for neighbor in graph[curNodeID]:
            nextNodeID = neighbor[0]
            costToNextNode = costFromSrc + price[nextNodeID]
            # 增加时间消耗
            nexttimeFromSrc = timeFromSrc + neighbor[1]
            if nexttimeFromSrc>maxtime:
                continue
            # 更新 dp table
            if nodeNumTo[nextNodeID] > costToNextNode:
                nodeNumTo[nextNodeID] = costToNextNode
                distTo[nextNodeID] = min(distTo[nextNodeID],nexttimeFromSrc)
                heapq.heappush(pq, State(nextNodeID, costToNextNode, nexttimeFromSrc))

            elif distTo[nextNodeID]>nexttimeFromSrc:
                heapq.heappush(pq, State(nextNodeID, costToNextNode, nexttimeFromSrc))
                distTo[nextNodeID] = nexttimeFromSrc
            
    return -1

Explain

本题使用了带有优先队列的 Dijkstra 算法来寻找在规定时间内从起点到终点的最小费用路径。首先，构建一个图来表示城市之间的道路和通行时间。然后，使用 Dijkstra 算法，通过优先队列来优先处理费用较小的路径。在遍历过程中，记录每个节点到起点的最小费用和最短时间，如果到达某个节点的路径费用更小或者时间更短，则更新该节点的信息并将其加入优先队列中继续遍历。最终，如果能在规定时间内到达终点，则返回最小费用，否则返回 -1。

时间复杂度: O(E + VlogV)

空间复杂度: O(V + E)

class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        n = len(passingFees)
        graph = [[] for _ in range(n)]
        for edge in edges:
            from_ = edge[0]
            to_ = edge[1]
            time = edge[2]
            graph[from_].append([to_, time])
            graph[to_].append([from_,time])

        return dijkstra(graph, 0, maxTime, n-1, passingFees)


class State:
    def __init__(self, id_: int, costFromSrc: int, timeFromSrc: int):
        self.id = id_
        self.costFromSrc = costFromSrc
        self.timeFromSrc = timeFromSrc

    def __lt__(self, other):
        return self.costFromSrc < other.costFromSrc


def dijkstra(graph: List[List[int]], src: int, maxtime: int, dst: int,price) -> int:
    distTo = [float('inf')] * len(graph)
    nodeNumTo = [float('inf')] * len(graph)
    distTo[src] = 0
    nodeNumTo[src] = price[src]

    pq = []
    heapq.heappush(pq, State(src, price[0], 0))

    while pq:
        curState = heapq.heappop(pq)
        curNodeID = curState.id
        costFromSrc = curState.costFromSrc
        timeFromSrc = curState.timeFromSrc

        if costFromSrc > nodeNumTo[curNodeID] and timeFromSrc > distTo[curNodeID]:
            continue

        if timeFromSrc > maxtime:
            continue

        if curNodeID == dst:
            return costFromSrc

        for neighbor in graph[curNodeID]:
            nextNodeID = neighbor[0]
            costToNextNode = costFromSrc + price[nextNodeID]
            nexttimeFromSrc = timeFromSrc + neighbor[1]
            if nexttimeFromSrc > maxtime:
                continue
            if nodeNumTo[nextNodeID] > costToNextNode:
                nodeNumTo[nextNodeID] = costToNextNode
                distTo[nextNodeID] = min(distTo[nextNodeID], nexttimeFromSrc)
                heapq.heappush(pq, State(nextNodeID, costToNextNode, nexttimeFromSrc))
            elif distTo[nextNodeID] > nexttimeFromSrc:
                heapq.heappush(pq, State(nextNodeID, costToNextNode, nexttimeFromSrc))
                distTo[nextNodeID] = nexttimeFromSrc

    return -1

Explore

在Dijkstra算法中，使用优先队列（最小堆）是为了能够快速从所有待处理的节点中选出当前费用最小的节点进行下一步扩展。这种选择策略是Dijkstra算法的核心，它保证了算法能够有效地按照从源点到各节点的最小费用顺序进行扩展，从而确保当我们首次访问到终点节点时，得到的路径费用就是最小的。如果使用普通队列或栈，则无法保证按照费用优先的顺序处理节点，可能会导致算法效率降低，需要处理更多的节点才能确定最短路径。

在本题中，我们不仅需要保证路径的总费用最小，同时还要求路径的总时间不超过一个给定的最大时间（`maxTime`）。因此，在更新节点信息时，我们需要同时考虑费用和时间。如果到达某个节点的新路径的费用更低或者时间更短，我们就需要更新该节点的最佳费用和时间记录。这种双重检查确保了我们能找到在时间限制内费用最小的路径。

这个条件检查帮助我们避免对已经找到更优解的节点进行重复和无效的处理。如果当前节点的费用高于已记录的最小费用，并且当前时间也高于已记录的最短时间，那么这条路径显然不会比已找到的路径更优，因此可以直接跳过，不需要将其扩展。这种剪枝操作可以显著减少优先队列中的操作次数，提高算法的总体效率。

Dijkstra算法通过持续更新到每个节点的最小费用和最短时间来确保找到最优路径。即使存在多条具有相同起点和终点但耗时不同的道路，算法也会考虑通过这些不同的道路到达终点的所有可能性。每次从优先队列中取出一个节点时，都会考虑从该节点出发的所有邻接节点，并更新这些节点的最佳到达费用和时间。通过这种方式，算法能够在所有可能的路径中选择出费用最低且满足时间限制的路径。