难度: Medium
Submission
运行时间: 31 ms
内存: 17.1 MB
class Solution:
def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:
k, conn, res, heap = k+1, [[] for _ in range(n+1)], [0]*(n+1), [(apple, i) for i,apple in enumerate(appleCost,1)]
for u,v,cost in roads:
conn[u].append((v,cost))
conn[v].append((u,cost))
heapify(heap)
while heap and n:
cur, node = heappop(heap)
if res[node]: continue
res[node], n = cur, n-1
for nxt, cost in conn[node]:
if not res[nxt]:
heappush(heap, (cur+cost*k, nxt))
return res[1:]
Explain
此题解采用了优先队列（最小堆）结合图的遍历来寻找购买苹果的最低成本。首先，题解中扩展了每条边的成本，将其变成原始成本乘以一个因子k+1。这是因为题目可能包含某种与k相关的特殊计算规则，比如运输成本或额外税费，但题目描述中未明确。接着使用了一个最小堆来保持当前苹果成本最低的节点。算法从成本最低的苹果开始，并通过遍历所有连接的节点来更新它们到达的成本，如果找到更小的成本则更新。重复这个过程直到所有节点都被访问过。最终，返回每个节点的最小成本。
时间复杂度: O((n + e) log n)
空间复杂度: O(n + e)
class Solution:
def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:
k, conn, res, heap = k+1, [[] for _ in range(n+1)], [0]*(n+1), [(apple, i) for i,apple in enumerate(appleCost,1)]
# 构建无向图的邻接表
for u,v,cost in roads:
conn[u].append((v,cost))
conn[v].append((u,cost))
# 初始化堆
heapify(heap)
# 使用优先队列处理最小成本计算
while heap and n:
cur, node = heappop(heap)
# 如果节点已经处理过，跳过
if res[node]: continue
# 设置当前节点的最低成本
res[node], n = cur, n-1
# 更新连接节点的成本
for nxt, cost in conn[node]:
if not res[nxt]:
heappush(heap, (cur+cost*k, nxt))
# 返回除0号节点外的所有节点成本
return res[1:]
Explore
在算法中，每条边的成本乘以因子k+1是为了模拟额外的成本因素，可能是因为题目涉及到的特殊运输成本或其他费用，这个因子k+1有助于模拟这种额外开销。这种处理方式确实与题目中的特定需求相关，可能题目描述中有提及特定的成本计算规则，但在题目摘要中未详细说明。这个因子使得算法可以灵活调整各条边的权重，以适应题目的特殊要求。
在处理优先队列时，跳过已经设置成本的节点是因为使用了贪心策略，即已经从堆中提取出的节点被认为其成本已经是最小的。如果一个节点的成本已经确定，再次考虑它将是多余的，因为其它路径到达该节点的成本一定不会更低。这种策略通常不会导致错过真正的最小成本，因为每个节点的成本一旦被设置，就意味着我们已找到从起点到该节点的最低成本路径。然而，如果算法实现中有错误，比如更新邻接节点成本的逻辑不正确，可能会导致不准确的结果。
在这种情况下，使用最小堆（优先队列）可以更有效地管理和更新节点的成本。最小堆能够保证每次从堆中提取的都是当前成本最低的节点，这对于实现像 Dijkstra 算法这样的最短路径算法非常关键。相比之下，如果使用数组，每次查找最小成本节点都需要遍历整个数组，效率较低；而如果使用二叉搜索树，虽然可以提供较快的插入和删除操作，但在维护平衡和更新操作方面比最小堆复杂。因此，最小堆在处理此类问题时，提供了既高效又简单的解决方案。