难度: Medium
Submission
运行时间: 260 ms
内存: 29.9 MB
### 网：dijkstra+dp(折扣)
from collections import defaultdict
import heapq
class Solution:
def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
g=defaultdict(list)
for x,y,w in highways:
g[x].append([y,w])
g[y].append([x,w])
dist=[[float("inf")]*(discounts+1) for _ in range(n)]
q=[(0,0,-1,discounts)]
while q:
dis,x,fa,k=heapq.heappop(q)
if x==n-1:
return dis
for y,w in g[x]:
if y==fa:
continue
if dist[y][k]>dis+w:
dist[y][k]=dis+w
heapq.heappush(q,(dist[y][k],y,x,k))
if k>0 and dist[y][k-1]>dis+w//2:
dist[y][k-1]=dis+w//2
heapq.heappush(q,(dist[y][k-1],y,x,k-1))
return -1
Explain
该题解使用了Dijkstra算法结合动态规划来解决最小费用寻路问题。首先，建立图的邻接表。然后，使用一个优先队列（通过heapq实现）来进行最小距离的贪心选择。维护一个二维数组dist，其中dist[i][j]表示到达节点i使用了j次折扣的最小费用。从源点开始，每次从优先队列中选出当前费用最小的点进行扩展，考虑两种情况：不使用折扣和使用折扣（如果剩余折扣次数大于0）。如果通过当前路线得到的新费用小于已记录的费用，则更新费用，并将新状态加入队列。如果到达终点，则返回当前的费用。若队列为空仍未到达终点，则返回-1表示无法到达。
时间复杂度: O((E+V) * log(V) * D)
空间复杂度: O(E + V * D)
### 网：dijkstra+dp(折扣)
from collections import defaultdict
import heapq
class Solution:
def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
g=defaultdict(list)
for x,y,w in highways:
g[x].append([y,w])
g[y].append([x,w])
dist=[[float('inf')] * (discounts + 1) for _ in range(n)]
q=[(0,0,-1,discounts)]
while q:
dis, x, fa, k = heapq.heappop(q)
if x == n-1:
return dis
for y, w in g[x]:
if y == fa:
continue
if dist[y][k] > dis + w:
dist[y][k] = dis + w
heapq.heappush(q, (dist[y][k], y, x, k))
if k > 0 and dist[y][k-1] > dis + w // 2:
dist[y][k-1] = dis + w // 2
heapq.heappush(q, (dist[y][k-1], y, x, k-1))
return -1
Explore
在这种实现中，我们使用一个二维数组`dist`来记录每个节点在不同折扣次数下的最小费用。对于每个节点`x`，每当从`x`扩展到邻接节点`y`时，我们会考虑两种情况：一是直接连接不使用折扣，二是使用一次折扣（如果折扣次数`k`大于0）。我们会检查通过当前路径到达`y`（无论是使用折扣还是不使用）得到的新费用是否比`dist[y][k]`（或`dist[y][k-1]`）更小。如果是，我们就更新相应的费用，并将这个新状态（包括新的费用、节点、父节点和剩余折扣次数）加入优先队列。这种方法确保了每个节点的费用在考虑折扣的情况下都能得到正确且最优的更新。
在每次扩展节点时，我们同时考虑使用折扣和不使用折扣两种情况，并比较哪种选择可以获得较低的费用。具体来说，对于每一个邻接节点`y`和边的权重`w`，我们不仅考虑`dis + w`（不使用折扣的费用），还考虑`dis + w // 2`（使用一次折扣的费用），前提是剩余折扣次数`k`大于0。我们会比较这两个值与当前记录在`dist[y][k]`和`dist[y][k-1]`中的值，然后选择更小的一个来更新。这种决策基于贪心算法的优化逻辑，旨在每一步都选择当前可能的最小费用。
这一设计主要是为了避免无意义的循环更新，即防止算法在相邻的两个节点之间来回更新，造成不必要的计算和可能的错误。当我们从节点`x`向节点`y`进行扩展时，如果`y`又回到了`x`的父节点`fa`，则意味着我们正在尝试重新进入已经处理过的路径，这并不会产生更优的结果，反而可能导致算法效率降低。因此，跳过这种情况可以减少冗余操作，提高算法效率，同时保持算法逻辑的清晰和正确性。