1.题目基本信息

1.1.题目描述

一组公路连接 n 个城市，城市编号为从 0 到 n - 1 。 输入包含一个二维数组 highways ，其中 highways[i] = [city1i, city2i, tolli] 表示有一条连接城市 city1i 和 city2i 的双向公路，允许汽车缴纳值为 tolli 的费用从 city1i 前往 city2i 或 从 city2i 前往 city1i 。

另给你一个整数 discounts 表示你最多可以使用折扣的次数。你可以使用一次折扣使通过第 ith 条公路的费用降低至 tolli / 2（向下取整）。 最多只可使用 discounts 次折扣， 且 每条公路最多只可使用一次折扣 。

返回从城市0 前往城市 n - 1 的 最小费用 。如果不存在从城市0 前往城市 n - 1 的路径，返回 -1 。

1.2.题目地址

https://leetcode.cn/problems/minimum-cost-to-reach-city-with-discounts/description/

2.解题方法

2.1.解题思路

Dijkstra算法

2.2.解题步骤

第一步，使用常规的方法构建dijkstra，采用堆模式

• 1.1.构建邻接表形式的图

第二步，使用堆进行遍历。堆中结点的形式为(结点到start的结点的距离,当前结点,剩余的折扣数)

• 2.1.从堆中弹出最近的结点

• 2.2.过滤掉堆中在costs中已经存在更近的距离的结点（第一个从堆中弹出(node,remainDiscounts)的一定是最近的）

• 2.3.在到达终点时，进行退出

• 2.4.更新当前状态的最短距离

• 2.5.遍历邻结点并将新的结点压入堆中（分为不使用折扣的结点和使用折扣的虚拟结点）

第三步，没法到达终点的情况

3.解题代码

python代码

from collections import defaultdict
from heapq import heappush, heappop

class Solution:
    def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
        # 同类型Dijkstra题目：Leetcode LCP 35. 电动车游城市
        # 思路：Dijkstra算法变体
        # 第一步，使用常规的方法构建dijkstra，采用堆模式
        # 1.1.构建邻接表形式的图
        graph = defaultdict(list)
        for u, v, weight in highways:
            graph[u].append((v, weight))
            graph[v].append((u, weight))
        # 第二步，使用堆进行遍历。堆中结点的形式为(结点到start的结点的距离,当前结点,剩余的折扣数)
        heap = [(0, 0, discounts)]
        costs = {}
        while heap:
            # 2.1.从堆中弹出最近的结点
            dist, node, remainDiscounts = heappop(heap)
            # 2.2..过滤掉堆中在costs中已经存在更近的距离的结点（第一个从堆中弹出(node,remainDiscounts)的一定是最近的）
            if (node, remainDiscounts) in costs:
                continue
            # 2.3.在到达终点时，进行退出
            if node == n - 1:
                return dist
            # 2.4.更新当前状态的最短距离
            costs[(node, remainDiscounts)] = dist
            # 2.5.遍历邻结点并将新的结点压入堆中（分为不使用折扣的结点和使用折扣的虚拟结点）
            for neigh, weight_ in graph[node]:
                heappush(heap, (dist + weight_, neigh, remainDiscounts))
                if remainDiscounts > 0:
                    heappush(heap, (dist + int(weight_ / 2), neigh, remainDiscounts - 1))
        # 第三步，没法到达终点的情况
        return -1

4.执行结果