题目描述
思路解析
一句话答案：LeetCode 1976 到达目的地的方案数：Dijkstra 求 0 到 n−1 的最短用时，松弛时同步计数——更短则条数整盘继承、等长则累加，条数对 1e9+7 取模，时间 O((n+e)log n)、空间 O(n+e)。
1976 数的到底是哪一种路径
n 个路口，roads[i]=[u,v,time] 是一条走 time 的双向路，问 0 到 n−1 用时恰好等于最短用时（总耗时最小的值）的路径有几条，条数对 1e9+7 取模（除以它取余数，防大数存不下）。示例 n=3、roads=[[0,1,1],[1,2,1],[0,2,2]]：直达 0→2 花 2，绕 0→1→2 也花 2，并列最短，输出 2。
把每条路径都走一遍为什么数不完
路径条数随岔口指数膨胀——每多一个能绕的中间点走法成倍翻，逐条搜出来比用时数不完；大量路径还共用前半程，同一截被反复重算。真正要的只有两个量：各点的最短用时，和凑出它的路数。
dist 旁边为什么还要养一个 ways
最短用时交给 Dijkstra（经典最短路算法）：每轮把离起点最近、还没定死的点定下来，拿它改善邻居，候选放优先队列（一个每次都能弹出当前最小值的容器）。条数是搭在它身上的一层 DP（动态规划，把子答案存表复用：dist[v] 记 0 到 v 的最短用时，ways[v] 记凑出这个用时的路径条数）。起点 dist[0]=0、ways[0]=1，到自己只有原地不动这一种。
更短继承、等长累加，怎么保证一条不多一条不少
弹出距离最小的点 u，对 u 的每个邻居 v（这条边耗时 w）做松弛——用经 u 的新用时 nd=dist[u]+w 试探 dist[v]：更短，到 v 的旧走法全体作废，dist[v]=nd、条数整盘改写 ways[v]=ways[u]；相等，又冒出一批同样短的路，ways[v]=(ways[v]+ways[u]) 再取模；更长，不动。
相加不重不漏的底气在出队顺序：近的点先弹出定死，u 出队那一刻 ways[u] 已把它所有最短前驱数齐；经 u 与经别的等距前驱到 v 的路，最后一步不同，天然不会重。
n=3 的小图，堆弹三次就见分晓
起手 dist=[0,∞,∞]、ways=[1,0,0]，堆里放 (0,0)。弹出 0：边 0-1 得 nd=0+1=1 比 ∞ 短，dist[1]=1、ways[1]=ways[0]=1；边 0-2 得 nd=0+2=2 也更短，dist[2]=2、ways[2]=1。弹出 1：边 1-2 得 nd=1+1=2 恰好等于 dist[2]，累加 ways[2]=1+1=2。弹出 2，邻居已无可改善。收尾 ways[2]=2，两条并列最短都数上，对上输出 2。
过期的堆记录不扔，条数为什么会数多
同一个点会带着新旧距离反复进堆，弹出时要核对 d 仍等于 dist[u]，不等即过期记录、直接扔——拿旧距离接着累加，同一批路会数两遍。等长写成覆盖也出错：示例里先到的直达路被丢，答案由 2 缩成 1。C++、Java 还得把 dist 存 long，初值用足够大的常量而非真无穷，免得相加溢出。
开销和裸 Dijkstra 同级：每条边至多入堆一次，堆操作 O(log n)（大 O 是数据翻倍时工作量跟几倍的记法），时间 O((n+e)log n)，e 为边数；边表加 dist、ways 和堆，空间 O(n+e)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「更短覆盖、等长累加」这两条松弛规则,下面逐帧套它。
初始化:起点 0 的最短距离 dist[0]=0、最短路条数 ways[0]=1(到自己只有空路这一种)。其余点距离记 ∞、条数 0。把 (距离 0, 节点 0) 放进优先队列。终点是节点 4。
从队列取出距离最小的节点 0(距离 0)并定下来:它的最短距离 0、最短路条数 1 已确定。下面看它每条边,松弛邻居。
0-1(耗时 1):到 1 的新距离 = 0+1 = 1,比原来的 ∞ 更短。更新 dist[1]=1,条数整盘继承 ways[1]=ways[0]=1(旧路全作废),并入队。
0-2(耗时 1):到 2 的新距离 = 0+1 = 1,比原来的 ∞ 更短。更新 dist[2]=1,条数整盘继承 ways[2]=ways[0]=1(旧路全作废),并入队。
0-3(耗时 2):到 3 的新距离 = 0+2 = 2,比原来的 ∞ 更短。更新 dist[3]=2,条数整盘继承 ways[3]=ways[0]=1(旧路全作废),并入队。
从队列取出距离最小的节点 1(距离 1)并定下来:它的最短距离 1、最短路条数 1 已确定。下面看它每条边,松弛邻居。
1-0 这条边(耗时 1):邻居 0 已定下,跳过。
1-4(耗时 2):到 4 的新距离 = 1+2 = 3,比原来的 ∞ 更短。更新 dist[4]=3,条数整盘继承 ways[4]=ways[1]=1(旧路全作废),并入队。
从队列取出距离最小的节点 2(距离 1)并定下来:它的最短距离 1、最短路条数 1 已确定。下面看它每条边,松弛邻居。
2-0 这条边(耗时 1):邻居 0 已定下,跳过。
2-4(耗时 2):到 4 的新距离 = 1+2 = 3,恰好等于已有的 dist[4]=3。又发现一条同样短的路!条数累加 ways[4] = 1+ways[2](1) = 2。
从队列取出距离最小的节点 3(距离 2)并定下来:它的最短距离 2、最短路条数 1 已确定。下面看它每条边,松弛邻居。
3-0 这条边(耗时 2):邻居 0 已定下,跳过。
3-4(耗时 1):到 4 的新距离 = 2+1 = 3,恰好等于已有的 dist[4]=3。又发现一条同样短的路!条数累加 ways[4] = 2+ways[3](1) = 3。
从队列取出距离最小的节点 4(距离 3)并定下来:它的最短距离 3、最短路条数 3 已确定。下面看它每条边,松弛邻居。
4-1 这条边(耗时 2):邻居 1 已定下,跳过。
4-2 这条边(耗时 2):邻居 2 已定下,跳过。
4-3 这条边(耗时 1):邻居 3 已定下,跳过。
队列处理完毕。终点节点 4 的最短距离 = 3,最短路条数 ways[4] = 3。这 3 条最短路分别经 1、2、3 三个中转点(0→1→4、0→2→4、0→3→4),长度都恰为 3。
答案就是 ways[n−1] = ways[4] = 3(本题规模内未触发取模)。关键在松弛时分清「更短就覆盖条数、等长就累加条数」,Dijkstra 的逐点定值顺序保证每个点被定下时,它的条数已经把所有最短前驱都数齐了。
边界:单点 1;唯一路 1;同长两条累加成 2。
两个延伸:0 权要特判;可在最短路 DAG 上 DP 数路径。
参考代码
from typing import Listimport heapqclass Solution: def countPaths(self, n: int, roads: List[List[int]]) -> int: MOD = 10**9 + 7 g = [[] for _ in range(n)] for a, b, w in roads: g[a].append((b, w)); g[b].append((a, w)) dist = [10**30] * n ways = [0] * n dist[0] = 0; ways[0] = 1 heap = [(0, 0)] while heap: d, u = heapq.heappop(heap) if d != dist[u]: continue for v, w in g[u]: nd = d + w if nd < dist[v]: dist[v] = nd ways[v] = ways[u] heapq.heappush(heap, (nd, v)) elif nd == dist[v]: ways[v] = (ways[v] + ways[u]) % MOD return ways[n - 1]复杂度
- 时间：O((n+e)·log n)，e 条边,每条最多触发一次入堆,堆操作 O(log n);维护 ways 只是常数附加,整体仍是带堆 Dijkstra 的 O((n+e)log n)
- 空间：O(n+e)，邻接表 O(n+e),dist 与 ways 各 O(n),堆最坏 O(e),合计 O(n+e)
易错点
面试追问把动画讲成自己的话
追问如果边权可能为 0,这套计数还对吗?
追问能不能不用 Dijkstra,改成在最短路 DAG 上做 DP 数路径?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找到所有的农场组
LeetCode 1992 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题