地图上有 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))