LeetCode 题解工作台
到达目的地的方案数
你在一个城市里，城市由 n 个路口组成，路口编号为 0 到 n - 1 ，某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。 给你一个整数 n 和二维整数数组 roads ，其中 roads[i] = [u i , v i , time i ]…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 动态·规划
答案摘要
我们定义以下几个数组，其中： - `g` 表示图的邻接矩阵，`g[i][j]` 表示点 `i` 到点 `j` 的最短路径长度，初始时全部为 ，而 `g[0][0]` 为 ；然后我们遍历 `roads`，将 `g[u][v]` 和 `g[v][u]` 更新为 `t`；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 动态·规划 题型思路
题目描述
你在一个城市里，城市由 n 个路口组成，路口编号为 0 到 n - 1 ，某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。
给你一个整数 n 和二维整数数组 roads ，其中 roads[i] = [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。
请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 109 + 7 取余 后返回。
示例 1：
输入：n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]] 输出：4 解释：从路口 0 出发到路口 6 花费的最少时间是 7 分钟。 四条花费 7 分钟的路径分别为： - 0 ➝ 6 - 0 ➝ 4 ➝ 6 - 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6 - 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
示例 2：
输入：n = 2, roads = [[1,0,10]] 输出：1 解释：只有一条从路口 0 到路口 1 的路，花费 10 分钟。
提示：
1 <= n <= 200n - 1 <= roads.length <= n * (n - 1) / 2roads[i].length == 30 <= ui, vi <= n - 11 <= timei <= 109ui != vi- 任意两个路口之间至多有一条路。
- 从任意路口出发，你能够到达其他任意路口。
解题思路
方法一：朴素 Dijkstra 算法
我们定义以下几个数组，其中：
g表示图的邻接矩阵，g[i][j]表示点i到点j的最短路径长度，初始时全部为 ，而g[0][0]为 ；然后我们遍历roads，将g[u][v]和g[v][u]更新为t；dist[i]表示从起点到点i的最短路径长度，初始时全部为 ，而dist[0]为 ；f[i]表示从起点到点i的最短路径的条数，初始时全部为 ，而f[0]为 ；vis[i]表示点i是否已经被访问过，初始时全部为False。
然后，我们使用朴素 Dijkstra 算法求出从起点到终点的最短路径长度，过程中同时记录下每个点的最短路径的条数。
最后，我们返回 f[n - 1] 即可。由于答案可能很大，我们需要对 取模。
时间复杂度 ，空间复杂度 。其中 为点的个数。
class Solution:
def countPaths(self, n: int, roads: List[List[int]]) -> int:
g = [[inf] * n for _ in range(n)]
for u, v, t in roads:
g[u][v] = g[v][u] = t
g[0][0] = 0
dist = [inf] * n
dist[0] = 0
f = [0] * n
f[0] = 1
vis = [False] * n
for _ in range(n):
t = -1
for j in range(n):
if not vis[j] and (t == -1 or dist[j] < dist[t]):
t = j
vis[t] = True
for j in range(n):
if j == t:
continue
ne = dist[t] + g[t][j]
if dist[j] > ne:
dist[j] = ne
f[j] = f[t]
elif dist[j] == ne:
f[j] += f[t]
mod = 10**9 + 7
return f[-1] % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N^3) |
| 空间 | O(N^2) |
面试官常问的追问
外企场景- question_mark
The candidate effectively uses dynamic programming to calculate the number of shortest paths.
- question_mark
The candidate demonstrates understanding of graph algorithms and topological sorting.
- question_mark
The candidate correctly handles modular arithmetic and edge cases involving multiple shortest paths.
常见陷阱
外企场景- error
Failing to handle multiple shortest paths correctly.
- error
Incorrect use of the topological order when updating the dynamic programming table.
- error
Not applying modular arithmetic as specified in the problem statement.
进阶变体
外企场景- arrow_right_alt
Consider a version where roads have different weights or are directed.
- arrow_right_alt
Implement an optimized version using BFS for unweighted graphs.
- arrow_right_alt
Extend the problem to calculate the number of paths in graphs with cycles.