number-of-restricted-paths-from-first-to-last-node

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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] = [ui, vi, weighti]</code> denotes that there is an edge between nodes <code>ui</code> and <code>vi</code> with weight equal to <code>weighti</code>.

A path from node <code>start</code> to node <code>end</code> is a sequence of nodes <code>[z0, z1, z2, ..., zk]</code> such that <code>z0 = start</code> and <code>zk = end</code> and there is an edge between <code>zi</code> and <code>zi+1</code> where <code>0 &lt;= i &lt;= k-1</code>.

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 restricted path is a path that also satisfies that <code>distanceToLastNode(zi) &gt; distanceToLastNode(zi+1)</code> where <code>0 &lt;= i &lt;= k-1</code>.

Return the number of restricted paths from node <code>1</code> to node <code>n</code>. Since that number may be too large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/17/restricted_paths_ex1.png" style="width: 351px; height: 341px;" />
<pre>
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]]
Output: 3
Explanation: Each circle contains the node number in black and its <code>distanceToLastNode value in blue. </code>The three restricted paths are:
1) 1 --&gt; 2 --&gt; 5
2) 1 --&gt; 2 --&gt; 3 --&gt; 5
3) 1 --&gt; 3 --&gt; 5
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/17/restricted_paths_ex22.png" style="width: 356px; height: 401px;" />
<pre>
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]]
Output: 1
Explanation: Each circle contains the node number in black and its <code>distanceToLastNode value in blue. </code>The only restricted path is 1 --&gt; 3 --&gt; 7.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 104</code></li>
	<li><code>n - 1 &lt;= edges.length &lt;= 4 * 104</code></li>
	<li><code>edges[i].length == 3</code></li>
	<li><code>1 &lt;= ui, vi &lt;= n</code></li>
	<li><code>ui != vi</code></li>
	<li><code>1 &lt;= weighti &lt;= 105</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>

countRestrictedPaths

Number of Restricted Paths From First to Last Node

All Ancestors of a Node in a Directed Acyclic Graph

all-ancestors-of-a-node-in-a-directed-acyclic-graph

有向无环图中一个节点的所有祖先

Design Graph With Shortest Path Calculator

design-graph-with-shortest-path-calculator

设计可以求最短路径的图类

Minimum Cost of a Path With Special Roads

minimum-cost-of-a-path-with-special-roads

前往目标的最小代价

Graph

Topological Sort

Dynamic Programming

Shortest Path

Heap (Priority Queue)

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

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

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

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

 

示例 1：
<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/03/07/restricted_paths_ex1.png" style="width: 351px; height: 341px;" />
<pre>
输入：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
</pre>

示例 2：
<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/03/07/restricted_paths_ex22.png" style="width: 356px; height: 401px;" />
<pre>
输入：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 。</pre>

 

提示：

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