难度: Medium
Submission
运行时间: 49 ms
内存: 17.9 MB
class Solution:
def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:
marked = set(marked)
g = [[] for _ in range(n)]
for a, b, c in edges:
g[a].append((b, c))
D = defaultdict(lambda: inf)
q = [(0, s)]
while q:
d, node = heappop(q)
if node in marked:
return d
if d > D[node]: continue
D[node] = d
for v, c in g[node]:
if D[v] > d + c:
D[v] = d + c
heappush(q, (d + c, v))
return -1
Explain
该题解采用了带优先级队列的Dijkstra算法来寻找从起点s到任意标记节点的最短距离。首先，将所有标记节点存储在集合中以便快速检查。接着，构建图的邻接表表示，然后使用一个优先队列（最小堆）来维护当前节点到起点的距离。每次从队列中取出距离最小的节点，如果该节点是标记节点，则直接返回其距离。否则，更新其邻接节点的距离，并将更新后的距离和节点推入队列中。如果遍历完所有可达节点后未找到标记节点，则返回-1。
时间复杂度: O((V + E) log V)
空间复杂度: O(V + E)
# 解决方案类
class Solution:
def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:
# 将标记节点转换为集合以便快速查找
marked = set(marked)
# 创建图的邻接表
g = [[] for _ in range(n)]
for a, b, c in edges:
g[a].append((b, c))
# 使用字典记录从起点到各节点的最短距离，默认为无穷大
D = defaultdict(lambda: inf)
# 使用优先队列（最小堆）来维护节点距离，开始时只包含起点
q = [(0, s)]
while q:
# 弹出当前堆顶元素，即最近的节点
d, node = heappop(q)
# 如果当前节点是标记节点，返回其距离
if node in marked:
return d
# 如果当前距离已不是最优距离，则跳过
if d > D[node]: continue
# 更新当前节点的最短距离
D[node] = d
# 遍历当前节点的所有邻接节点
for v, c in g[node]:
# 如果可以通过当前节点更新邻接节点的距离，则进行更新并入堆
if D[v] > d + c:
D[v] = d + c
heappush(q, (d + c, v))
# 如果所有节点处理完毕没有返回，说明没有任何标记节点是可达的
return -1
Explore
Dijkstra算法的核心目的是从起点出发逐步扩展路径，直至找到目标节点的最短路径。在这个过程中，优先队列（最小堆）被用来高效地获取当前未处理节点中距离起点最近的节点。这是因为优先队列能够保证每次从中取出的都是具有最小距离的节点，这样可以确保算法按照从近到远的顺序处理节点，有效地实现贪心策略。使用其他数据结构如数组或链表虽然也可以实现类似功能，但需要线性时间来查找最小元素，而优先队列的插入和删除操作通常是对数时间复杂度，因此更适合实现Dijkstra算法。
在Dijkstra算法实现中，如果一个节点的当前处理距离大于已记录的最短距离，说明该距离已被更新过且存在更优的路径。因此跳过这样的节点可以避免重复处理和不必要的计算，进而提高算法效率。这种策略不会导致节点距离更新错误，因为一旦节点的最短距离被确定并记录，后续出现的更长的距离不会对结果产生影响。这是因为Dijkstra算法的贪心性质保证了一旦找到最短路径，就不会有更短的路径出现于后续的操作中。
在题解中返回-1作为标记节点不可达的信号是一种常见的做法，这帮助调用者区分找到有效路径与无法到达任何标记节点的场景。这种设计简洁明了，适用于多数情况，特别是在需要明确区分处理结果的情况下。然而，其他可能的设计包括返回一个更详细的错误码、异常处理或是返回一个包含状态信息的复杂对象（如路径长度和状态描述），这些都可以根据具体应用需求和上下文环境来决定。
将标记节点转换为集合可以大幅提高查找效率。在集合中，查找操作通常是平均时间复杂度为O(1)的，这是因为集合内部通过哈希表实现。相比之下，在列表中查找一个元素的时间复杂度为O(n)，因为可能需要遍历整个列表来找到一个元素或确认元素不存在。特别是在标记节点数量较多或查找操作频繁的情况下，使用集合可以显著降低算法的总体时间复杂度。