LeetCode每日一题——882. 细分图中的可到达节点

简介: 给你一个无向图(原始图),图中有 n 个节点,编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链,每条边之间的新节点数各不相同。

题目

给你一个无向图(原始图),图中有 n 个节点,编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链,每条边之间的新节点数各不相同。

图用由边组成的二维数组 edges 表示,其中 edges[i] = [ui, vi, cnti] 表示原始图中节点 ui 和 vi 之间存在一条边,cnti 是将边 细分 后的新节点总数。注意,cnti == 0 表示边不可细分。

要 细分 边 [ui, vi] ,需要将其替换为 (cnti + 1) 条新边,和 cnti 个新节点。新节点为 x1, x2, …, xcnti ,新边为 [ui, x1], [x1, x2], [x2, x3], …, [xcnti+1, xcnti], [xcnti, vi] 。

现在得到一个 新的细分图 ,请你计算从节点 0 出发,可以到达多少个节点?如果节点间距离是 maxMoves 或更少,则视为 可以到达 。

给你原始图和 maxMoves ,返回 新的细分图中从节点 0 出发 可到达的节点数 。

示例

示例 1:

2345_image_file_copy_13.jpg

输入:edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3 输出:13

解释:边的细分情况如上图所示。 可以到达的节点已经用黄色标注出来。

示例 2:

输入:edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4

输出:23

示例 3:

输入:edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n

= 5

输出:1

解释:节点 0 与图的其余部分没有连通,所以只有节点 0 可以到达。

提示:

0 <= edges.length <= min(n * (n - 1) / 2, 104)

edges[i].length == 3

0 <= ui < vi < n

图中 不存在平行边

0 <= cnti <= 104

0 <= maxMoves <= 109

1 <= n <= 3000

思路

迪杰斯特拉算法:


2345_image_file_copy_14.jpg

题解

class Solution:
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
        g = defaultdict(list)
        for u, v, cnt in edges:
            g[u].append((v, cnt + 1))
            g[v].append((u, cnt + 1))
        q = [(0, 0)]
        dist = [0] + [inf] * n
        while q:
            d, u = heappop(q)
            for v, cnt in g[u]:
                if (t := d + cnt) < dist[v]:
                    dist[v] = t
                    q.append((t, v))
        ans = sum(d <= maxMoves for d in dist)
        for u, v, cnt in edges:
            a = min(cnt, max(0, maxMoves - dist[u]))
            b = min(cnt, max(0, maxMoves - dist[v]))
            ans += min(cnt, a + b)
        return ans
目录
相关文章
|
1月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
17 0
LeetCode第二十四题(两两交换链表中的节点)
|
1月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
40 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
1月前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
15 0
|
3月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
|
3月前
|
Python
【Leetcode刷题Python】450. 删除二叉搜索树中的节点
LeetCode上538号问题"把二叉搜索树转换为累加树"的Python实现,使用反向中序遍历并记录节点值之和来更新每个节点的新值。
38 4
【Leetcode刷题Python】450. 删除二叉搜索树中的节点
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
52 5
|
3月前
|
Python
【Leetcode刷题Python】222. 完全二叉树的节点个数
LeetCode第222题"完全二叉树的节点个数"的Python代码实现,通过递归和深度优先遍历的方法来计算给定完全二叉树的节点总数。
38 5
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
41 4
|
5月前
|
算法 数据可视化 数据挖掘
哈希表+DFS快速解决力扣129题:求根节点到叶节点数字之和
哈希表+DFS快速解决力扣129题:求根节点到叶节点数字之和
|
6月前
|
存储
【LeetCode】剑指 Offer 54. 二叉搜索树的第k大节点
【LeetCode】剑指 Offer 54. 二叉搜索树的第k大节点
47 1