到达目的地的方案数 图解题解
这道题到底在问什么
- 输入
- n=3, roads=[[0,1,1],[1,2,1],[0,2,2]]
- 输出
- 2(直达 0→2 与中转 0→1→2 都长 2)
- 输入
- n=2, roads=[[1,0,10]]
- 输出
- 1(唯一一条路)
最优解：一步一步想明白
- 3记住「更短覆盖、等长累加」这两条松弛规则,下面逐帧套它。
- 4初始化:起点 0 的最短距离 dist[0]=0、最短路条数 ways[0]=1(到自己只有空路这一种)。其余点距离记 ∞、条数 0。把 (距离 0, 节点 0) 放进优先队列。终点是节点 4。
- 5从队列取出距离最小的节点 0(距离 0)并定下来:它的最短距离 0、最短路条数 1 已确定。下面看它每条边,松弛邻居。
- 60-1(耗时 1):到 1 的新距离 = 0+1 = 1,比原来的 ∞ 更短。更新 dist[1]=1,条数整盘继承 ways[1]=ways[0]=1(旧路全作废),并入队。
- 70-2(耗时 1):到 2 的新距离 = 0+1 = 1,比原来的 ∞ 更短。更新 dist[2]=1,条数整盘继承 ways[2]=ways[0]=1(旧路全作废),并入队。
- 80-3(耗时 2):到 3 的新距离 = 0+2 = 2,比原来的 ∞ 更短。更新 dist[3]=2,条数整盘继承 ways[3]=ways[0]=1(旧路全作废),并入队。
- 9从队列取出距离最小的节点 1(距离 1)并定下来:它的最短距离 1、最短路条数 1 已确定。下面看它每条边,松弛邻居。
- 101-0 这条边(耗时 1):邻居 0 已定下,跳过。
- 111-4(耗时 2):到 4 的新距离 = 1+2 = 3,比原来的 ∞ 更短。更新 dist[4]=3,条数整盘继承 ways[4]=ways[1]=1(旧路全作废),并入队。
- 12从队列取出距离最小的节点 2(距离 1)并定下来:它的最短距离 1、最短路条数 1 已确定。下面看它每条边,松弛邻居。
- 132-0 这条边(耗时 1):邻居 0 已定下,跳过。
- 142-4(耗时 2):到 4 的新距离 = 1+2 = 3,恰好等于已有的 dist[4]=3。又发现一条同样短的路!条数累加 ways[4] = 1+ways[2](1) = 2。
- 15从队列取出距离最小的节点 3(距离 2)并定下来:它的最短距离 2、最短路条数 1 已确定。下面看它每条边,松弛邻居。
- 163-0 这条边(耗时 2):邻居 0 已定下,跳过。
- 173-4(耗时 1):到 4 的新距离 = 2+1 = 3,恰好等于已有的 dist[4]=3。又发现一条同样短的路!条数累加 ways[4] = 2+ways[3](1) = 3。
- 18从队列取出距离最小的节点 4(距离 3)并定下来:它的最短距离 3、最短路条数 3 已确定。下面看它每条边,松弛邻居。
- 194-1 这条边(耗时 2):邻居 1 已定下,跳过。
- 204-2 这条边(耗时 2):邻居 2 已定下,跳过。
- 214-3 这条边(耗时 1):邻居 3 已定下,跳过。
- 22队列处理完毕。终点节点 4 的最短距离 = 3,最短路条数 ways[4] = 3。这 3 条最短路分别经 1、2、3 三个中转点(0→1→4、0→2→4、0→3→4),长度都恰为 3。
- 23答案就是 ways[n−1] = ways[4] = 3(本题规模内未触发取模)。关键在松弛时分清「更短就覆盖条数、等长就累加条数」,Dijkstra 的逐点定值顺序保证每个点被定下时,它的条数已经把所有最短前驱都数齐了。
⚠️ 容易写错的地方
✗ 错：发现更短路时忘了重置 ways
✓ 对：nd 更小则 ways[v]=ways[u](整盘继承)
更短路出现后,旧距离对应的所有计数都作废,必须把条数换成新前驱的条数,而不是累加
✗ 错：把「等长」也写成覆盖
✓ 对：nd 等于 dist[v] 要累加 ways[v]+=ways[u]
等长说明又多了一批同样短的路,应在原有条数上加,不能覆盖,否则会漏数
✗ 错：dist 用真·无穷或 int 存导致溢出
✓ 对：用 long 与一个足够大的有限初值
C++、Java 里相加可能越界;用 long 且初值取 LLONG_MAX/4 之类既够大又不会加爆
完整代码（Python / C++ / Java）
Python
from typing import List
import heapq
class 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]C++
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
int countPaths(int n, vector<vector<int>>& roads) {
const int MOD = 1000000007;
vector<vector<pair<int,int>>> g(n);
for (auto &e : roads) { g[e[0]].push_back({e[1], e[2]}); g[e[1]].push_back({e[0], e[2]}); }
vector<long long> dist(n, LLONG_MAX / 4), ways(n);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
dist[0] = 0; ways[0] = 1; pq.push({0, 0});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d != dist[u]) continue;
for (auto [v, w] : g[u]) {
long long nd = d + w;
if (nd < dist[v]) { dist[v] = nd; ways[v] = ways[u]; pq.push({nd, v}); }
else if (nd == dist[v]) ways[v] = (ways[v] + ways[u]) % MOD;
}
}
return ways[n - 1];
}
};Java
import java.util.*;
class Solution {
public int countPaths(int n, int[][] roads) {
int MOD = 1_000_000_007;
List<int[]>[] g = new ArrayList[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] e : roads) { g[e[0]].add(new int[]{e[1], e[2]}); g[e[1]].add(new int[]{e[0], e[2]}); }
long[] dist = new long[n], ways = new long[n];
Arrays.fill(dist, Long.MAX_VALUE / 4);
PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
dist[0] = 0; ways[0] = 1; pq.offer(new long[]{0, 0});
while (!pq.isEmpty()) {
long[] cur = pq.poll();
long d = cur[0]; int u = (int) cur[1];
if (d != dist[u]) continue;
for (int[] e : g[u]) {
int v = e[0], w = e[1];
long nd = d + w;
if (nd < dist[v]) { dist[v] = nd; ways[v] = ways[u]; pq.offer(new long[]{nd, v}); }
else if (nd == dist[v]) ways[v] = (ways[v] + ways[u]) % MOD;
}
}
return (int) 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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 到达目的地的方案数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果边权可能为 0,这套计数还对吗?+
本题道路耗时为正,标准 Dijkstra 计数直接成立、无需担心。若扩展到允许 0 权边,边跑边累加就不再可靠:权为 0 时 u 和 v 可能距离相等却互为前驱,弹出顺序不再保证「前驱先定」,会少数或重复计数。正确做法是先用 Dijkstra 求出所有点的最短距离,再在「最短路子图」(只保留满足 dist[u]+w==dist[v] 的边)上按距离分层做拓扑计数;对其中由 0 权边连成的等距连通块还要专门处理。这类扩展超出本题范围。
能不能不用 Dijkstra,改成在最短路 DAG 上做 DP 数路径?+
可以。先用一遍 Dijkstra 求出所有点的最短距离,再把满足 dist[u]+w==dist[v] 的边保留下来,它们构成一张有向无环图(最短路 DAG)。在这张 DAG 上从起点做拓扑序 DP:cnt[v] = 各前驱 cnt[u] 之和,起点 cnt=1。结果与边跑边累加完全一致,只是分成了两阶段。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 到达目的地的方案数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。