LeetCode 题解工作台
从第一个节点出发到最后一个节点的受限路径数
现有一个加权无向连通图。给你一个正整数 n ，表示图中有 n 个节点，并按从 1 到 n 给节点编号；另给你一个数组 edges ，其中每个 edges[i] = [u i , v i , weight i ] 表示存在一条位于节点 u i 和 v i 之间的边，这条边的权重为 weight i 。…
5
题型
4
代码语言
3
相关题
当前训练重点
中等 · 动态·规划
答案摘要
class Solution: def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 动态·规划 题型思路
题目描述
现有一个加权无向连通图。给你一个正整数 n ，表示图中有 n 个节点，并按从 1 到 n 给节点编号；另给你一个数组 edges ，其中每个 edges[i] = [ui, vi, weighti] 表示存在一条位于节点 ui 和 vi 之间的边，这条边的权重为 weighti 。
从节点 start 出发到节点 end 的路径是一个形如 [z0, z1, z2, ..., zk] 的节点序列，满足 z0 = start 、zk = end 且在所有符合 0 <= i <= k-1 的节点 zi 和 zi+1 之间存在一条边。
路径的距离定义为这条路径上所有边的权重总和。用 distanceToLastNode(x) 表示节点 n 和 x 之间路径的最短距离。受限路径 为满足 distanceToLastNode(zi) > distanceToLastNode(zi+1) 的一条路径，其中 0 <= i <= k-1 。
返回从节点 1 出发到节点 n 的 受限路径数 。由于数字可能很大，请返回对 109 + 7 取余 的结果。
示例 1：
输入：n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]] 输出：3 解释：每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。三条受限路径分别是： 1) 1 --> 2 --> 5 2) 1 --> 2 --> 3 --> 5 3) 1 --> 3 --> 5
示例 2：
输入：n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]] 输出：1 解释：每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。唯一一条受限路径是：1 --> 3 --> 7 。
提示：
1 <= n <= 2 * 104n - 1 <= edges.length <= 4 * 104edges[i].length == 31 <= ui, vi <= nui != vi1 <= weighti <= 105- 任意两个节点之间至多存在一条边
- 任意两个节点之间至少存在一条路径
解题思路
方法一：堆优化 Dijkstra + 记忆化搜索
class Solution:
def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
@cache
def dfs(i):
if i == n:
return 1
ans = 0
for j, _ in g[i]:
if dist[i] > dist[j]:
ans = (ans + dfs(j)) % mod
return ans
g = defaultdict(list)
for u, v, w in edges:
g[u].append((v, w))
g[v].append((u, w))
q = [(0, n)]
dist = [inf] * (n + 1)
dist[n] = 0
mod = 10**9 + 7
while q:
_, u = heappop(q)
for v, w in g[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heappush(q, (dist[v], v))
return dfs(1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ensure the candidate is comfortable with both graph traversal techniques and dynamic programming.
- question_mark
Look for a clear understanding of why Dijkstra’s algorithm is applied in reverse for this problem.
- question_mark
The candidate should demonstrate knowledge of how to handle large numbers with modular arithmetic.
常见陷阱
外企场景- error
Not using Dijkstra's algorithm in reverse order, which leads to incorrect path calculations.
- error
Forgetting to apply the modulo operation when the number of paths becomes large.
- error
Improper handling of the dynamic programming state, which may result in an incorrect count of restricted paths.
进阶变体
外企场景- arrow_right_alt
Consider variations of the problem where the graph is directed, requiring different approaches to track restricted paths.
- arrow_right_alt
Introduce additional constraints such as path length limits or restrictions on the number of hops between nodes.
- arrow_right_alt
Explore the problem by relaxing the condition on restricted paths, allowing non-decreasing path weights.