leetcode
leetcode 1751 ~ 1800
到达目的地的方案数

到达目的地的方案数

难度:

标签:

题目描述

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

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

请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 109 + 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 <= ui, vi <= n - 1
  • 1 <= timei <= 109
  • ui != vi
  • 任意两个路口之间至多有一条路。
  • 从任意路口出发，你能够到达其他任意路口。

代码结果

运行时间: 40 ms, 内存: 23.8 MB

/*
 * 题目思路：
 * 1. 使用Dijkstra算法计算从路口0到路口n-1的最短路径。
 * 2. 使用Java Streams来初始化和处理图结构。
 * 3. 初始化时，将起点0的时间设为0，路径数目设为1。
 * 4. 使用优先队列维护未处理节点，根据最短时间优先处理。
 * 5. 对于每个节点，更新其邻接节点的时间和路径数目。
 * 6. 将最终结果取模10^9+7返回。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    private static final int MOD = 1000000007;

    public int countPaths(int n, int[][] roads) {
        List<List<int[]>> graph = IntStream.range(0, n)
                                           .mapToObj(i -> new ArrayList<int[]>())
                                           .collect(Collectors.toList());
        Arrays.stream(roads).forEach(road -> {
            graph.get(road[0]).add(new int[]{road[1], road[2]});
            graph.get(road[1]).add(new int[]{road[0], road[2]});
        });

        int[] minTime = new int[n];
        Arrays.fill(minTime, Integer.MAX_VALUE);
        int[] count = new int[n];
        minTime[0] = 0;
        count[0] = 1;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{0, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];
            int time = current[1];

            if (time > minTime[u]) continue;

            graph.get(u).forEach(neighbor -> {
                int v = neighbor[0];
                int newTime = time + neighbor[1];

                if (newTime < minTime[v]) {
                    minTime[v] = newTime;
                    count[v] = count[u];
                    pq.offer(new int[]{v, newTime});
                } else if (newTime == minTime[v]) {
                    count[v] = (count[v] + count[u]) % MOD;
                }
            });
        }

        return count[n - 1];
    }
}

解释

方法:

此题解采用了类似Dijkstra算法的变种，目的是找出从起点到终点的最短路径及其数量。首先，建立邻接表e存储图，dis数组记录从起点到每个点的最短距离，ways数组记录达到每个点的最短路径的数量。使用优先队列（最小堆）来持续处理当前未处理的最近的节点。每次从队列中取出当前距离最小的节点，更新其相邻节点的最短距离和路径数量。更新逻辑是：如果找到更短的路径，则更新最短路径和重置路径计数；如果距离相等，则累加路径数量。最终，ways数组的最后一个元素即为从起点到终点的最短路径的数量。

时间复杂度:

O((V+E) log V)

空间复杂度:

O(V+E)

代码细节讲解

🦆
在算法中`dis`数组和`ways`数组的初始化方式有何区别，以及这种初始化对算法的影响是什么？
▷
`dis`数组用于记录从起点到每个节点的最短距离，初始化为无穷大（除了起点为0），这确保了任何比当前记录更短的路径都会被考虑。`ways`数组用于记录到达每个节点的最短路径的数量，其初始化方式是起点为1，其他所有节点为0，表示从起点到起点的路径只有一条，而到达其他节点的路径数未知，初始为0。这种初始化对算法的影响是确保了只有当找到到某节点的有效路径时，该节点的路径数才会更新，避免了无效路径的计数。
🦆
为什么选择使用优先队列（最小堆）来实现这个算法，而不是使用其他数据结构如普通队列或栈？
▷
优先队列（最小堆）被选择是因为它能够每次从队列中快速地获取当前未处理的最小距离节点，这是Dijkstra算法的核心要求，以此保证路径的最短性。使用普通队列或栈可能导致处理顺序不严格按照节点当前距离排序，从而无法保证每次都处理当前最短的路径，这会影响算法的正确性和效率。
🦆
在代码中，每次从优先队列中取出节点后，为什么要检查`cw <= dis[cv]`？这个条件的作用是什么？
▷
这个条件用于确认从优先队列中取出的节点（其代表一条到达该节点的路径）是否仍然是有效的最短路径。在算法运行过程中，同一个节点可能因为找到更短的路径而被多次加入队列。检查`cw <= dis[cv]`确保只有对应于当前已知最短路径的节点处理逻辑会执行，从而防止对过时的路径进行错误的路径数更新。
🦆
当发现一条到达某个节点的等长路径（即`cw + w == dis[v]`）时，你是如何更新路径数量的，这种方法可能会引入哪些计算上的错误？
▷
当出现等长路径时，算法通过累加路径数量`ways[v] = (ways[cv] + ways[v]) % mod`来更新。这种方法使用了模运算来避免整数溢出，保证结果在一个安全的数值范围内。可能的计算错误主要是如果忘记应用模运算，结果可能会超出整数的表示范围，导致溢出错误。

相关问题

最大方阵和划分数字的方案数