图论

• 2685
  • 完全连通分量的边数 = C(v,2)

dijkstra 时间复杂度： code: explanation: vid: https://www.youtube.com/watch?v=CL1byLngb5Q code: https://leetcode.cn/problems/network-delay-time/submissions/

 
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
 
	g = [[] for _ in range(n)]
	
	for x, y, d in times:
		g[x-1].append((y-1, d))
	
	dist = [inf]*n
	dist[k-1] =0
	h = [(0, k-1)]
 
	
	while h:
		dx, x = heappop(h)
		if dx>dist[x]:
			continue
		
		for y, dy in g[x]:
			if dy+dist[x] <dist[y]:
				dist[y] = dy+dist[x]
				heappush(h, (dist[y], y))
	return max(dist) if max(dist) != inf else -1

leetcode dj+dfs https://leetcode.com/list/53js48ke/

• 399