Package g1701_1800.s1786_number_of_restricted_paths_from_first_to_last_node

Class Solution

java.lang.Object

g1701_1800.s1786_number_of_restricted_paths_from_first_to_last_node.Solution

public class Solution
extends Object

1786 - Number of Restricted Paths From First to Last Node.<p>Medium</p> <p>There is an undirected weighted connected graph. You are given a positive integer <code>n</code> which denotes that the graph has <code>n</code> nodes labeled from <code>1</code> to <code>n</code>, and an array <code>edges</code> where each <code>edges[i] = [u_i, v_i, weight_i]</code> denotes that there is an edge between nodes <code>u_i</code> and <code>v_i</code> with weight equal to <code>weight_i</code>.</p> <p>A path from node <code>start</code> to node <code>end</code> is a sequence of nodes <code>[z₀, z₁, z₂, &hellip;, z_k]</code> such that <code>z₀ = start</code> and <code>z_k = end</code> and there is an edge between <code>z_i</code> and <code>z_i+1</code> where <code>0 <= i <= k-1</code>.</p> <p>The distance of a path is the sum of the weights on the edges of the path. Let <code>distanceToLastNode(x)</code> denote the shortest distance of a path between node <code>n</code> and node <code>x</code>. A <strong>restricted path</strong> is a path that also satisfies that <code>distanceToLastNode(z_i) > distanceToLastNode(z_i+1)</code> where <code>0 <= i <= k-1</code>.</p> <p>Return <em>the number of restricted paths from node</em> <code>1</code> <em>to node</em> <code>n</code>. Since that number may be too large, return it <strong>modulo</strong> <code>10⁹ + 7</code>.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/02/17/restricted_paths_ex1.png" alt="" /></p> <p><strong>Input:</strong> n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> Each circle contains the node number in black and its <code>distanceToLastNode value in blue.</code> The three restricted paths are:</p> <ol> <li> <p>1 &ndash;> 2 &ndash;> 5</p> </li> <li> <p>1 &ndash;> 2 &ndash;> 3 &ndash;> 5</p> </li> <li> <p>1 &ndash;> 3 &ndash;> 5</p> </li> </ol> <p><strong>Example 2:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/02/17/restricted_paths_ex22.png" alt="" /></p> <p><strong>Input:</strong> 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]]</p> <p><strong>Output:</strong> 1</p> <p><strong>Explanation:</strong> Each circle contains the node number in black and its <code>distanceToLastNode value in blue.</code> The only restricted path is 1 &ndash;> 3 &ndash;> 7.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= n <= 2 * 10⁴</code></li> <li><code>n - 1 <= edges.length <= 4 * 10⁴</code></li> <li><code>edges[i].length == 3</code></li> <li><code>1 <= u_i, v_i <= n</code></li> <li><code>u_i != v_i</code></li> <li><code>1 <= weight_i <= 10⁵</code></li> <li>There is at most one edge between any two nodes.</li> <li>There is at least one path between any two nodes.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	countRestrictedPaths(int n, int[][] edges)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

countRestrictedPaths

public int countRestrictedPaths(int n,
 int[][] edges)