package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
# README
882. Reachable Nodes In Subdivided Graph
Solution idea
Dijkstra
要点总结
cnt转化成weight -> 可用Dijkstra求大点之间至少需要多少步- 刨去Dijkstra求得的从起点到每个大点之间所用最少步数之后, 任意两个大点之间还可以走多少步 (一步就是一个小点):
(maxMoves-Dij[x])+(maxMoves-Dij[y])- 我的最初想法: 是把小点当作大点看待, 然后从起点开始用BFS计算最远可以到哪里. 但是问题有两个: 1. 小点要重新label和储存; 2. 题目给出的小点的量级为$10^4$, 用BFS太贵
- 转换思路: 如上图, 任意两个大点
x和y之间可以走到的小点个数分别是从x出发还可以走多少步 (i)+从y出发还可以走多少步 (j), 这样就可以利用上Dijkstra, 再遍历每条边计算小点就可以
Time Complexity = $O(E\log E)$