地图上有 m 条无向边，每条边 (x, y, w) 表示位置 m 到位置 y 的权值为 w。从位置 0 到 位置 n 可能有多条路径。我们定义一条路径的危险值为这条路径中所有的边的最大权值。请问从位置 0 到 位置 n 所有路径中最小的危险值为多少？
最小危险值为最小生成树中 0 到 n 路径上的最大边权。以此题为例给出最小生成树的两种经典算法。
- 算法 1: Kruskal's algorithm，使用并查集实现。
# Kruskal's algorithmclassSolution:
defgetMinRiskValue(self, N, M, X, Y, W):
# Kruskal's algorithm with union-findparent=list(range(N+1))
rank= [1] * (N+1)
deffind(x):
ifparent[parent[x]] !=parent[x]:
parent[x] =find(parent[x])
returnparent[x]
defunion(x, y):
px, py=find(x), find(y)
ifpx==py:
returnFalseifrank[px] >rank[py]:
parent[py] =pxelifrank[px] <rank[py]:
parent[px] =pyelse:
parent[px] =pyrank[py] +=1returnTrueedges=sorted(zip(W, X, Y))
forw, x, yinedges:
ifunion(x, y) andfind(0) ==find(N): # early return without constructing MSTreturnw- 算法 2: Prim's algorithm，使用优先级队列 (堆)实现
# Prim's algorithmclassSolution:
defgetMinRiskValue(self, N, M, X, Y, W):
# construct graphadj=collections.defaultdict(list)
foriinrange(M):
adj[X[i]].append((Y[i], W[i]))
adj[Y[i]].append((X[i], W[i]))
# Prim's algorithm with min heapMST=collections.defaultdict(list)
min_heap= [(w, 0, v) forv, winadj[0]]
heapq.heapify(min_heap)
whileNnotinMST:
w, p, v=heapq.heappop(min_heap)
ifvnotinMST:
MST[p].append((v, w))
MST[v].append((p, w))
forn, winadj[v]:
ifnnotinMST:
heapq.heappush(min_heap, (w, v, n))
# dfs to search route from 0 to ndfs= [(0, None, float('-inf'))]
whiledfs:
v, p, max_w=dfs.pop()
forn, winMST[v]:
cur_max_w=max(max_w, w)
ifn==N:
returncur_max_wifn!=p:
dfs.append((n, v, cur_max_w))