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

问题描述

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

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

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

请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 10⁹ + 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 <= 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)到各点的最短距离，然后使用记忆化搜索来计算路径数量；

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

代码

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