上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
}
};
python3 解法, 执行用时: 240 ms, 内存消耗: 22.2 MB, 提交时间: 2022-11-26 10:58:22
class Solution:
def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
adList = defaultdict(list)
for u, v, nodes in edges:
adList[u].append([v, nodes])
adList[v].append([u, nodes])
used = {}
visited = set()
reachableNodes = 0
pq = [[0, 0]]
while pq and pq[0][0] <= maxMoves:
step, u = heapq.heappop(pq)
if u in visited:
continue
visited.add(u)
reachableNodes += 1
for v, nodes in adList[u]:
if nodes + step + 1 <= maxMoves and v not in visited:
heappush(pq, [nodes + step + 1, v])
used[(u, v)] = min(nodes, maxMoves - step)
for u, v, nodes in edges:
reachableNodes += min(nodes, used.get((u, v), 0) + used.get((v, u), 0))
return reachableNodes
golang 解法, 执行用时: 160 ms, 内存消耗: 9.9 MB, 提交时间: 2022-11-26 10:58:04
func reachableNodes(edges [][]int, maxMoves, n int) int {
adList := map[int][][]int{}
for _, edge := range edges {
u, v, nodes := edge[0], edge[1], edge[2]
adList[u] = append(adList[u], []int{v, nodes})
adList[v] = append(adList[v], []int{u, nodes})
}
used := map[int]int{}
visited := map[int]bool{}
reachableNodes := 0
pq := myHeap{}
heap.Push(&pq, []int{0, 0})
for pq.Len() > 0 && pq[0][0] <= maxMoves {
p := heap.Pop(&pq).([]int)
step, u := p[0], p[1]
if visited[u] {
continue
}
visited[u] = true
reachableNodes++
for _, q := range adList[u] {
v, nodes := q[0], q[1]
if nodes+step+1 <= maxMoves && !visited[v] {
heap.Push(&pq, []int{nodes + step + 1, v})
}
used[u*n+v] = min(nodes, maxMoves-step)
}
}
for _, edge := range edges {
u, v, nodes := edge[0], edge[1], edge[2]
reachableNodes += min(nodes, used[u*n+v]+used[v*n+u])
}
return reachableNodes
}
func min(x, y int) int {
if x > y {
return y
}
return x
}
type myHeap [][]int
func (h myHeap) Len() int {
return len(h)
}
func (h myHeap) Less(i, j int) bool {
return h[i][0] < h[j][0]
}
func (h myHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *myHeap) Push(val interface{}) {
*h = append(*h, val.([]int))
}
func (h *myHeap) Pop() interface{} {
hp := *h
val := hp[len(hp)-1]
*h = hp[:len(hp)-1]
return val
}
golang 解法, 执行用时: 68 ms, 内存消耗: 7.6 MB, 提交时间: 2022-11-26 10:57:33
func reachableNodes(edges [][]int, maxMoves, n int) (ans int) {
g := make([][]neighbor, n)
for _, e := range edges {
u, v, cnt := e[0], e[1], e[2]
g[u] = append(g[u], neighbor{v, cnt + 1})
g[v] = append(g[v], neighbor{u, cnt + 1}) // 建图
}
dist := dijkstra(g, 0) // 从 0 出发的最短路
for _, d := range dist {
if d <= maxMoves { // 这个点可以在 maxMoves 步内到达
ans++
}
}
for _, e := range edges {
u, v, cnt := e[0], e[1], e[2]
a := max(maxMoves-dist[u], 0)
b := max(maxMoves-dist[v], 0)
ans += min(a+b, cnt) // 这条边上可以到达的节点数
}
return
}
// 以下为 Dijkstra 算法模板
type neighbor struct{ to, weight int }
func dijkstra(g [][]neighbor, start int) []int {
dist := make([]int, len(g))
for i := range dist {
dist[i] = math.MaxInt32
}
dist[start] = 0
h := hp{{start, 0}}
for len(h) > 0 {
p := heap.Pop(&h).(pair)
x := p.x
if dist[x] < p.dist {
continue
}
for _, e := range g[x] {
y := e.to
if d := dist[x] + e.weight; d < dist[y] {
dist[y] = d
heap.Push(&h, pair{y, d})
}
}
}
return dist
}
type pair struct{ x, dist int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() (v interface{}) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }
func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if a < b { return b }; return a }
python3 解法, 执行用时: 148 ms, 内存消耗: 20.6 MB, 提交时间: 2022-11-26 10:57:17
class Solution:
def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
g = [[] for _ in range(n)]
for u, v, cnt in edges:
g[u].append((v, cnt + 1))
g[v].append((u, cnt + 1)) # 建图
dist = self.dijkstra(g, 0) # 从 0 出发的最短路
ans = sum(d <= maxMoves for d in dist) # 可以在 maxMoves 步内到达的点的个数
for u, v, cnt in edges:
a = max(maxMoves - dist[u], 0)
b = max(maxMoves - dist[v], 0)
ans += min(a + b, cnt) # 这条边上可以到达的节点数
return ans
# Dijkstra 算法模板
# 返回从 start 到每个点的最短路
def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:
dist = [inf] * len(g)
dist[start] = 0
h = [(0, start)]
while h:
d, x = heappop(h)
if d > dist[x]:
continue
for y, wt in g[x]:
new_d = dist[x] + wt
if new_d < dist[y]:
dist[y] = new_d
heappush(h, (new_d, y))
return dist
