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

2021-03-07

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

难度中等0

现有一个加权无向连通图。给你一个正整数 n ，表示图中有 n 个节点，并按从 1 到 n 给节点编号；另给你一个数组 edges ，其中每个 edges[i] = [ui, vi, weighti] 表示存在一条位于节点 ui 和 vi 之间的边，这条边的权重为 weighti 。

从节点 start 出发到节点 end 的路径是一个形如 [z0, z1, z2, ..., zk] 的节点序列，满足 z0 = start 、zk = end 且在所有符合 0 <= i <= k-1 的节点 zi 和 zi+1 之间存在一条边。

路径的距离定义为这条路径上所有边的权重总和。用 distanceToLastNode(x) 表示节点 n 和 x 之间路径的最短距离。受限路径 为满足 distanceToLastNode(zi) > distanceToLastNode(zi+1) 的一条路径，其中 0 <= i <= k-1 。

返回从节点 1 出发到节点 n 的 受限路径数 。由于数字可能很大，请返回对 109 + 7 取余的结果。

示例 1：

输入：n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
输出：3
解释：每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。三条受限路径分别是：
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5

示例 2：

1
2
3

输入：n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
输出：1
解释：每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。唯一一条受限路径是：1 --> 3 --> 7 。

提示：

1 <= n <= 2 * 104
n - 1 <= edges.length <= 4 * 104
edges[i].length == 3
1 <= ui, vi <= n
ui != vi
1 <= weighti <= 105
任意两个节点之间至多存在一条边
任意两个节点之间至少存在一条路径

Dijkstra

class Solution{
        public int countRestrictedPaths(int n, int[][] edges) {
        ArrayList<int[]>[] list = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }
        // 预处理数据，转换成邻接表存储
        for (int[] edge : edges) {
            list[edge[0] - 1].add(new int[] { edge[1] - 1, edge[2] });
            list[edge[1] - 1].add(new int[] { edge[0] - 1, edge[2] });
        }
        // dist用来保存i节点到n节点的最小距离
        // count用来保存从节点i到节点n的路径的数量
        Integer[] dist = new Integer[n], count = new Integer[n];

        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        // 将最后一个节点加入堆
        // 从最后一个节点开始向前遍历,如果遇到相邻节点就把相邻节点加入堆中
        queue.add(new int[] { n - 1, 0 });

        // 当堆不为空时
        while (!queue.isEmpty()) {
            // 获取顶的节点
            // 第一个值是节点
            // 第二个值是cost

            int[] head = queue.remove();
            // 如果没有计算过当前节点到节点n的距离
            if (dist[head[0]] == null) {
                // head[1]就是堆中到节点n最小的距离
                dist[head[0]] = head[1];

                // 如果可以到达节点n，那么路径数目是1，否则路径数目是0
                count[head[0]] = head[0] == n - 1 ? 1 : 0;

                // 对于当前节点的每个邻接节点
                for (int[] i : list[head[0]]) {
                    // 如果计算过他到n节点的路径数目并且他到n节点的距离小于当前节点到n节点的距离（题目中要求的条件），
                    // 那么更新当前节点到n节点的路径的数量
                    if (count[i[0]] != null && dist[i[0]] < head[1]) {
                        count[head[0]] = (count[head[0]] + count[i[0]]) % 1000000007;
                    }
                    // 将邻接节点加入到队列中去
                    queue.add(new int[] { i[0], i[1] + head[1] });
                }
            }
        }
        // 返回从节点1到节点n的满足条件的路径数
        return count[0];
    }
}

方法：堆优化Dijkstra + 记忆化搜索

class Solution {
 public int countRestrictedPaths(int n, int[][] edges) {
    int cnt = 0;
    Map<Integer, List<int[]>> map = new HashMap<>();
    // 初始化邻接表
    for (int[] t : edges) {
      int x = t[0];
      int y = t[1];
      if(x>y){
        int tmp = x;
        x = y;
        y = tmp;
      }
      map.computeIfAbsent(x, k -> new ArrayList<>()).add(new int[]{y, t[2]});
      map.computeIfAbsent(y, k -> new ArrayList<>()).add(new int[]{x, t[2]});
    }
    
    // 初始化dis数组和mem数组
    int[] dis = new int[n + 1];
    Long[] mem = new Long[n + 1];
    dis = findShortPath(map,n,n);

    cnt = (int)findLimitedPathCount(map,1,n,dis,mem);
    return cnt;
  }
  final int MOD = 1000000007;
  private long findLimitedPathCount(Map<Integer, List<int[]>> map, int i, int n, int[] dis, Long[] mem) {
    if(mem[i]!=null)return mem[i];
    if(i==n)return 1;
    long cnt = 0;
    List<int[]> list = map.getOrDefault(i,Collections.emptyList());
    for (int[] arr:list){
      int next = arr[0];
      if(dis[next]<dis[i]){
        cnt += findLimitedPathCount(map,next,n,dis,mem);
        cnt %= MOD;
      }
    }
    mem[i] = cnt;
    return cnt;
  }


  public int[] findShortPath( Map<Integer, List<int[]>> map, int n, int K) {
    // 初始化dis数组和vis数组
    int[] dis = new int[n + 1];
    Arrays.fill(dis, 0x3f3f3f3f);
    boolean[] vis = new boolean[n + 1];

    // 起点的dis为0，但是别忘记0也要搞一下，因为它是不参与的
    dis[K] = 0;
    dis[0] = 0;

    // new一个小堆出来，按照dis升序排，一定要让它从小到大排，省去了松弛工作
    PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> dis[o1] - dis[o2]);
    // 把起点放进去
    queue.offer(K);

    while (!queue.isEmpty()) {
      // 当队列不空，拿出一个源出来
      Integer poll = queue.poll();
      if(vis[poll]) continue;
      // 把它标记为访问过
      vis[poll] = true;
      // 遍历它的邻居们，当然可能没邻居，这里用getOrDefault处理就很方便
      List<int[]> list = map.getOrDefault(poll, Collections.emptyList());
      for (int[] arr : list) {
        int next = arr[0];
        // 如果这个邻居访问过了，继续
        if (vis[next]) continue;
        // 更新到这个邻居的最短距离，看看是不是当前poll出来的节点到它更近一点
        dis[next] = Math.min(dis[next], dis[poll] + arr[1]);
        queue.offer(next);
      }
    }
    return dis;
  }
}

作者：hu-li-hu-wai
链接：https://leetcode-cn.com/problems/number-of-restricted-paths-from-first-to-last-node/solution/dui-you-hua-dijkstra-ji-yi-hua-sou-suo-b-tif8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

补充知识

Dijkstra

1、将源点加入堆，并调整堆。

2、选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。

3、处理与u相邻的，未被访问过的，满足三角不等式的顶点

1) 若该点在堆里，更新距离，并调整该元素在堆中的位置。

2) 若该点不在堆里，加入堆，更新堆。

4、若取到的u为终点，结束算法；否则重复步骤2、3。

// 伪代码不能运行

//visit初始为0，防止回溯
int visit[] = new int[n+1];
//假设起点为src, 终点为dst, 图以二维矩阵的形式存储，若graph[i][j] == 0, 代表i,j不相连
int Dijkstra(int src, int dst, int[][] graph){
    PriorityQueue<Node> pq = new PriorityQueue<Node>();
    //将起点加入pq
    pq.add(new Node(src, 0));
    while(pq.size()){
        Node t = pq.poll();
        //当前节点是终点，即可返回最短路径
        if(t.node == dst) return t.cost;
        //若当前节点已遍历过，跳过当前节点
        if(visit[t.node]) continue;
        //将当前节点标记成已遍历
        visit[t.node] = 1;
        for(int i = 0; i < n; i++){
            if(graph[t.node][i] && !visited[i]){
                pq.add(new Node(i, t.cost + graph[t.node][i])); 
            }
        }
    }
    return -1
}

//定义一个存储节点和离起点相应距离的数据结构
class Node implements Comparator<Node> {
    public int node;
    public int cost;
   
    public Node()
    {
    }
   
    public Node(int node, int cost)
    {
        this.node = node;
        this.cost = cost;
    }
   
    @Override
    public int compare(Node node1, Node node2)
    {
        if (node1.cost < node2.cost)
            return -1;
        if (node1.cost > node2.cost)
            return 1;
        return 0;
    }
}

743. 网络延迟时间

难度中等231

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过有向边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：

1 2	输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 输出：2

示例 2：

1 2	输入：times = [[1,2,1]], n = 2, k = 1 输出：1

示例 3：

1 2	输入：times = [[1,2,1]], n = 2, k = 2 输出：-1

提示：

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都 互不相同（即，不含重复边）

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        Map<Integer, List<int[]>> graph = new HashMap();
        for (int[] edge: times) {
            if (!graph.containsKey(edge[0]))
                graph.put(edge[0], new ArrayList<int[]>());
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        PriorityQueue<int[]> heap = new PriorityQueue<int[]>(
                (info1, info2) -> info1[0] - info2[0]);
        heap.offer(new int[]{0, K});

        Map<Integer, Integer> dist = new HashMap();

        while (!heap.isEmpty()) {
            int[] info = heap.poll();
            int d = info[0], node = info[1];
            if (dist.containsKey(node)) continue;
            dist.put(node, d);
            if (graph.containsKey(node))
                for (int[] edge: graph.get(node)) {
                    int nei = edge[0], d2 = edge[1];
                    if (!dist.containsKey(nei))
                        heap.offer(new int[]{d+d2, nei});
                }
        }

        if (dist.size() != N) return -1;
        int ans = 0;
        for (int cand: dist.values())
            ans = Math.max(ans, cand);
        return ans;
    }

作者：LeetCode
链接：https://leetcode-cn.com/problems/network-delay-time/solution/wang-luo-yan-chi-shi-jian-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Dijkstra 算法题目
https://leetcode-cn.com/problems/network-delay-time/solution/