2024.3.5力扣每日一题——到达目的地的方案数

2024.3.5

- - 题目来源
  - 我的题解
  - - 方法一深度优先遍历（超时）
    - 方法二最短路径算法（Dijkstra 算法）+优先队列

题目来源

力扣每日一题；题序：1976

我的题解

方法一深度优先遍历（超时）

从节点0开始进行深度优先遍历，直到遍历到节点n-1结束，遍历过程记录路径和。

时间复杂度：O(E+m)。E表示边数，m表示节点数
空间复杂度：O(m+E)

java">TreeMap<Long,Long> map=new TreeMap<>();
public int countPaths(int n, int[][] roads) {
    List<Integer>[] g=createGraph(n,roads);
    boolean[] visited=new boolean[n];
    visited[0]=true;
    dfs(g,0,-1,0,visited,n);
    return (int)(map.firstEntry().getValue()%1000000007);

}
//构建图
public List<Integer>[] createGraph(int n,int[][] edges){
    List<Integer>[] g=new ArrayList[n];
    for(int i=0;i<n;i++){
        g[i]=new ArrayList<>();
    }
    for(int[] t:edges){
        int from = t[0];
        int to = t[1];
        int weight = t[2];
        g[from].add(to);
        g[from].add(weight);
        g[to].add(from);
        g[to].add(weight);
    }
    return g;
}
//深度优先遍历
public void dfs(List<Integer>[] g,int cur,int pre,long count,boolean[] visited,int n){
    if(cur==n-1)
        map.put(count,map.getOrDefault(count,0L)+1);
    for(int i=0;i<g[cur].size();i+=2){
        int next=g[cur].get(i);
        int weight=g[cur].get(i+1);
        if(!visited[next]){
            visited[next]=true;
            dfs(g,next,cur,count+weight,visited,n);
            visited[next]=false;
        }
    }
}

方法二最短路径算法（Dijkstra 算法）+优先队列

具体的实现可以看官方题解，我有点没看明白
传统的Dijkstra 算法可以求得两个节点之间的最短路径，但是本题要求求出和最短路径长度相同的路径数。因此，需要对Dijkstra算法进行一些优化。
观察优先队列实现的「Dijkstra 算法」，有以下数据结构：

e是邻接表，这道题中需要我们自己根据 roads 创建。
q 是优先队列，元素是路径长度和点的编号。不停往外抛出队列中的最短路径和点。如果这个点是未被确定最短路径的点，那么这次出队列的操作，就将确定源到这个点的最短路径。然后依次访问这个点相邻的点，判断从这个点到相邻的点的路径，是否能刷新源相邻点的最短路径，如果能，则将路径长度和相邻点放入队列。
dis 用来记录源到各个点当前最短路径的长度。会在访问当前出队列点的相邻点的过程中被刷新。
vis用来记录哪些点的最短路径已经被确定。在这里略显多余，可以用当前出队列的路径长度和点的最短路径的比较来代替。

除此之外，还需要一个新的数组 ways。ways[v] 就表示源到点 v最短的路径数目，且最短路径长度为 dis[v]。 ways的更新时机与 dis 相同。在访问当前点 u 的各个相邻点 v 时，

如果从点 u 到点 v 路径，能刷新 dis[v]，则更新 dis[v]，并将 ways[v] 更新为 ways[u]，表示有多少条源到点 u 的最短路径，就有多少条源到点 v的最短路径。
如果从点 u 到点 v 路径，与 dis[v]相等。那么 ways[v] 的值要加上 ways[u]，表示点 u 到点 v 路径贡献了另一部分源到点 v 的最短路径。
如果从点 u 到点 v 路径，大于 dis[v]。那么无需操作 dis[v]。

时间复杂度：O(mlogm)
空间复杂度：O(m)

java">public int countPaths(int n, int[][] roads) {
    int mod = 1000000007;
    List<int[]>[] e = new List[n];
    for (int i = 0; i < n; i++) {
        e[i] = new ArrayList<int[]>();
    }
    //构建图
    for (int[] road : roads) {
        int x = road[0], y = road[1], t = road[2];
        e[x].add(new int[]{y, t});
        e[y].add(new int[]{x, t});
    }
    // 节点0到每个节点的距离
    long[] dis = new long[n];
    Arrays.fill(dis, Long.MAX_VALUE);
    //表示源到其他节点的最短的路径数目，且最短路径长度为 dis
    int[] ways = new int[n];
	//使用
    PriorityQueue<long[]> pq = new PriorityQueue<long[]>((a, b) -> Long.compare(a[0], b[0]));
    pq.offer(new long[]{0, 0});
    //到本身的距离为0
    dis[0] = 0;
    //只有一个节点
    ways[0] = 1;

    while (!pq.isEmpty()) {
        long[] arr = pq.poll();
        long t = arr[0];
        int u = (int) arr[1];
       	//如果当前堆顶的距离大于现有节点位置，不用更新
        if (t > dis[u]) {
            continue;
        }
        //
        for (int[] next : e[u]) {
            int v = next[0], w = next[1];
            if (t + w < dis[v]) {
                dis[v] = t + w;
                ways[v] = ways[u];
                pq.offer(new long[]{t + w, v});
            } else if (t + w == dis[v]) {
                ways[v] = (ways[u] + ways[v]) % mod;
            }
        }
    }
    return ways[n - 1];
}