# 1976.到达目的地的方案数 (Medium)

## 问题描述
[1976. 到达目的地的方案数 (Medium)](https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/)

你在一个城市里，城市由 `n` 个路口组成，路口编号为 `0` 到 `n - 1` ，某些路口之间有 **双向**
道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。

给你一个整数 `n` 和二维整数数组 `roads` ，其中 `roads[i] = [uᵢ, vᵢ, timeᵢ]`
表示在路口 `uᵢ` 和 `vᵢ` 之间有一条需要花费 `timeᵢ` 时间才能通过的道路。你想知道花费
**最少时间** 从路口 `0` 出发到达路口 `n - 1` 的方案数。

请返回花费 **最少时间** 到达目的地的 **路径数目** 。由于答案可能很大，将结果对 `10⁹ + 7`
**取余** 后返回。

**示例 1：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065542.png)

```
输入：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 <= 200`
- `n - 1 <= roads.length <= n * (n - 1) / 2`
- `roads[i].length == 3`
- `0 <= uᵢ, vᵢ <= n - 1`
- `1 <= timeᵢ <= 10⁹`
- `uᵢ != vᵢ`
- 任意两个路口之间至多有一条路。
- 从任意路口出发，你能够到达其他任意路口。

## 解题思路
首先，利用**Dijkstra**算法求得点$n-1$到各点的最短距离，然后使用记忆化搜索来计算路径数量；

由于路径数限制需要花费最短时间，那么经过中间的点花费的时间也一定是最短的，最短路径上相邻两点之间的距离也一定是最短的，反过来也成立，路径上相邻两点之间的距离都是最短的，那么最终路径所花的时间也是最短的。

## 代码
```cpp
class Solution {
  public:
    int mod = 1000000007;
    void Dijkstra(vector<vector<vector<int>>> &graph, vector<long> &dis, int start_idx, vector<int> &is_min) {
        auto cmp = [&](pair<int, long> &p1, pair<int, long> &p2) {
            return p1.second > p2.second;
        };
        priority_queue<pair<int, long>, vector<pair<int, long>>, decltype(cmp)> pq(cmp);
        pq.push({start_idx, 0});
        while (!pq.empty()) {
            auto [idx, len] = pq.top();
            pq.pop();
            if (is_min[idx] == 1) {
                continue;
            }
            dis[idx] = len;  // 更新最短路
            is_min[idx] = 1; // 已找到最短路
            for (auto &vec : graph[idx]) {
                if (is_min[vec[0]] == 0) {
                    pq.push({vec[0], len + vec[1]});
                }
            }
        }
    }
    int dfs(vector<int> &used, vector<vector<vector<int>>> &graph, int idx, vector<long> &disn, vector<int> &cach) {
        if (idx == 0) {
            return 1;
        }
        if (cach[idx] != -1) {
            return cach[idx];
        }
        int res = 0;
        for (auto &vec : graph[idx]) {
            // 这个条件判断是关键，第一个表示下一个点也是最短的（可以忽略），第二个表示不会走回路，第三个表示每次走最短路径
            // if (dis0[vec[0]] + disn[vec[0]] == disn[0] && dis0[idx] > dis0[vec[0]] && vec[1] + disn[idx] == disn[vec[0]]) {
            if (vec[1] + disn[idx] == disn[vec[0]]) {
                res = (res + dfs(used, graph, vec[0], disn, cach)) % mod;
            }
        }
        cach[idx] = res;
        return cach[idx];
    }
    int countPaths(int n, vector<vector<int>> &roads) {
        vector<vector<vector<int>>> graph(n);
        for (auto &road : roads) {
            graph[road[0]].push_back({road[1], road[2]});
            graph[road[1]].push_back({road[0], road[2]});
        }
        vector<long> disn(n);   // 用于存储从n - 1开始的最短路径
        vector<int> is_minn(n); // 表示是否已经找到最短路径
        // Dijkstra(graph, dis0, 0, is_min0);
        Dijkstra(graph, disn, n - 1, is_minn);
        vector<int> used(n);
        vector<int> cach(n, -1);
        return dfs(used, graph, n - 1, disn, cach);
    }
};
```