从第一个节点出发到最后一个节点的受限路径数

/*
  题目思路：
  1. 使用Dijkstra算法计算从节点n到所有其他节点的最短距离。
  2. 使用Java Stream API简化遍历和过滤操作。
  3. 通过倒序DP计算从节点1到节点n的受限路径数。
*/

import java.util.*;
import java.util.stream.*;

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

    public int countRestrictedPaths(int n, int[][] edges) {
        // 构建图
        Map<Integer, List<int[]>> graph = IntStream.rangeClosed(0, n)
            .boxed()
            .collect(Collectors.toMap(i -> i, i -> new ArrayList<>()));
        Arrays.stream(edges).forEach(edge -> {
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
            graph.get(edge[1]).add(new int[]{edge[0], edge[2]});
        });

        // Dijkstra算法计算从n到所有其他节点的最短路径
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[n] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{n, 0});
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[0], d = curr[1];
            if (d > dist[u]) continue;
            graph.get(u).stream()
                .filter(next -> dist[next[0]] > dist[u] + next[1])
                .forEach(next -> {
                    int v = next[0], w = next[1];
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{v, dist[v]});
                });
        }

        // 使用DFS计算受限路径的数量
        Integer[] dp = new Integer[n + 1];
        return dfs(1, n, graph, dist, dp);
    }

    private int dfs(int node, int n, Map<Integer, List<int[]>> graph, int[] dist, Integer[] dp) {
        if (node == n) return 1;
        if (dp[node] != null) return dp[node];
        return dp[node] = graph.get(node).stream()
            .filter(next -> dist[node] > dist[next[0]])
            .map(next -> dfs(next[0], n, graph, dist, dp))
            .reduce(0, (a, b) -> (a + b) % MOD);
    }
}