到达目的地的方案数 图解题解

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)。

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];
    }
}