1786. Number of Restricted Paths From First to Last Node Medium

1/**
2 * [1786] Number of Restricted Paths From First to Last Node
3 *
4 * There is an undirected weighted connected graph. You are given a positive integer n which denotes that the graph has n nodes labeled from 1 to n, and an array edges where each edges[i] = [ui, vi, weighti] denotes that there is an edge between nodes ui and vi with weight equal to weighti.
5 * A path from node start to node end is a sequence of nodes [z0, z1, z2, ..., zk] such that z0 = start and zk = end and there is an edge between zi and zi+1 where 0 <= i <= k-1.
6 * The distance of a path is the sum of the weights on the edges of the path. Let distanceToLastNode(x) denote the shortest distance of a path between node n and node x. A restricted path is a path that also satisfies that distanceToLastNode(zi) > distanceToLastNode(zi+1) where 0 <= i <= k-1.
7 * Return the number of restricted paths from node 1 to node n. Since that number may be too large, return it modulo 10^9 + 7.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2021/02/17/restricted_paths_ex1.png" style="width: 351px; height: 341px;" />
11 * Input: n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
12 * Output: 3
13 * Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The three restricted paths are:
14 * 1) 1 --> 2 --> 5
15 * 2) 1 --> 2 --> 3 --> 5
16 * 3) 1 --> 3 --> 5
17 * 
18 * Example 2:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2021/02/17/restricted_paths_ex22.png" style="width: 356px; height: 401px;" />
20 * Input: 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]]
21 * Output: 1
22 * Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The only restricted path is 1 --> 3 --> 7.
23 * 
24 *  
25 * Constraints:
26 * 
27 * 	1 <= n <= 2 * 10^4
28 * 	n - 1 <= edges.length <= 4 * 10^4
29 * 	edges[i].length == 3
30 * 	1 <= ui, vi <= n
31 * 	ui != vi
32 * 	1 <= weighti <= 10^5
33 * 	There is at most one edge between any two nodes.
34 * 	There is at least one path between any two nodes.
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node/
40// discuss: https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn count_restricted_paths(n: i32, edges: Vec<Vec<i32>>) -> i32 {
46        0
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_1786() {
58    }
59}
60