快速公交

难度: Hard

小扣打算去秋日市集，由于游客较多，小扣的移动速度受到了人流影响： - 小扣从 `x` 号站点移动至 `x + 1` 号站点需要花费的时间为 `inc`； - 小扣从 `x` 号站点移动至 `x - 1` 号站点需要花费的时间为 `dec`。现有 `m` 辆公交车，编号为 `0` 到 `m-1`。小扣也可以通过搭乘编号为 `i` 的公交车，从 `x` 号站点移动至 `jump[i]*x` 号站点，耗时仅为 `cost[i]`。小扣可以搭乘任意编号的公交车且搭乘公交次数不限。假定小扣起始站点记作 `0`，秋日市集站点记作 `target`，请返回小扣抵达秋日市集最少需要花费多少时间。由于数字较大，最终答案需要对 1000000007 (1e9 + 7) 取模。注意：小扣可在移动过程中到达编号大于 `target` 的站点。 **示例 1：** >输入：`target = 31, inc = 5, dec = 3, jump = [6], cost = [10]` > >输出：`33` > >解释： >小扣步行至 1 号站点，花费时间为 5； >小扣从 1 号站台搭乘 0 号公交至 6 * 1 = 6 站台，花费时间为 10； >小扣从 6 号站台步行至 5 号站台，花费时间为 3； >小扣从 5 号站台搭乘 0 号公交至 6 * 5 = 30 站台，花费时间为 10； >小扣从 30 号站台步行至 31 号站台，花费时间为 5； >最终小扣花费总时间为 33。 **示例 2：** >输入：`target = 612, inc = 4, dec = 5, jump = [3,6,8,11,5,10,4], cost = [4,7,6,3,7,6,4]` > >输出：`26` > >解释： >小扣步行至 1 号站点，花费时间为 4； >小扣从 1 号站台搭乘 0 号公交至 3 * 1 = 3 站台，花费时间为 4； >小扣从 3 号站台搭乘 3 号公交至 11 * 3 = 33 站台，花费时间为 3； >小扣从 33 号站台步行至 34 站台，花费时间为 4； >小扣从 34 号站台搭乘 0 号公交至 3 * 34 = 102 站台，花费时间为 4； >小扣从 102 号站台搭乘 1 号公交至 6 * 102 = 612 站台，花费时间为 7； >最终小扣花费总时间为 26。 **提示：** - `1 <= target <= 10^9` - `1 <= jump.length, cost.length <= 10` - `2 <= jump[i] <= 10^6` - `1 <= inc, dec, cost[i] <= 10^6`

Submission

运行时间: 56 ms

内存: 17.8 MB

class Solution:
    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:
        # (cost, station)
        pq = [(0, target)]
        visited_stations = set()
        ans = inf
        while pq:
            total_cost, station = heappop(pq)
            #print(total_cost, station, ans)
            if total_cost > ans:
                break
            if station == 0:
                ans = total_cost
                break
            if station in visited_stations:
                continue
            visited_stations.add(station)
            ans = min(ans, total_cost + station * inc)
            
            for j, c in zip(jump, cost):
                d, m = divmod(station, j)
                if d not in visited_stations:
                    heappush(pq, (m * inc + total_cost + c, d))
                if d + 1 not in visited_stations:
                    heappush(pq, ((j - m) * dec + total_cost + c, d + 1))
        return ans % (10 ** 9 + 7)

Explain

本题解采用了优先队列（最小堆）结合广度优先搜索的方法来寻找到达目标站点的最小花费。初始时，将目标站点放入优先队列，代表从目标站点逆向回到起点的代价为零（逆向思维）。然后逐渐将所有可能的站点及其花费压入优先队列。对于每个站点，计算直接步行到起点的花费，以及通过公交车跳跃后的新站点和对应花费。每次从优先队列中取出当前花费最小的站点，更新答案，并检查是否已到起点。如果达到起点站，记录总花费并结束搜索。否则，继续探索下一跳的可能站点。利用visited_stations集合避免重复处理同一站点，以优化搜索效率。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:
        # 初始化优先队列和访问集合
        pq = [(0, target)]
        visited_stations = set()
        ans = inf
        # 处理每个状态
        while pq:
            total_cost, station = heappop(pq)
            # 如果当前费用已经超过已知最小值，终止处理
            if total_cost > ans:
                break
            # 到达起点站，更新最小费用
            if station == 0:
                ans = total_cost
                break
            if station in visited_stations:
                continue
            visited_stations.add(station)
            # 直接步行到起点的费用
            ans = min(ans, total_cost + station * inc)
            # 通过每种公交车处理新的状态
            for j, c in zip(jump, cost):
                d, m = divmod(station, j)
                # 跳跃后站点不在访问集合中，则加入优先队列
                if d not in visited_stations:
                    heappush(pq, (m * inc + total_cost + c, d))
                if d + 1 not in visited_stations:
                    heappush(pq, ((j - m) * dec + total_cost + c, d + 1))
        return ans % (10 ** 9 + 7)

Explore

逆向搜索的核心思想是将目标视为起点，从而逆向考虑到达实际起点的路径和费用。这种方法通过每次优先处理费用最小的站点（使用优先队列），确保了首先考虑的路径总是当前可能的最小费用路径。逆向处理允许算法在找到到达起点的可行路径时，已经确保这是花费最小的路径，因为所有后续考虑的路径都将具有更高的起始费用。这种策略有效地减少了搜索空间，并优化了性能。

在算法执行过程中，如果某个站点的处理费用`total_cost`已经超过了之前找到的最小费用`ans`，那么继续处理这个站点只会导致更高的总费用。因为从这个站点出发的任何进一步路径都会基于这个已经较高的`total_cost`，无法产生比`ans`更低的结果。基于最小堆的性质，队列中剩余的所有站点的开始处理费用也都不会低于当前的`total_cost`。因此，可以安全地忽略或停止处理费用已超标的站点，从而提高算法的效率。

优先队列（最小堆）在这类问题中的主要优势在于它能够保证每次从队列中取出的都是当前未处理站点中费用最小的一个。这种特性使得算法在每一步都优先考虑当前可能的最低成本路径，从而有效地找到全局最优解。此外，使用优先队列还可以高效地管理和更新待处理的站点集合，尤其是在涉及大量数据和频繁更新时，最小堆能够在对数时间内完成插入和删除最小元素操作，极大地优化了性能。