number-of-ways-to-arrive-at-destination

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are in a city that consists of <code>n</code> intersections numbered from <code>0</code> to <code>n - 1</code> with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.

You are given an integer <code>n</code> and a 2D integer array <code>roads</code> where <code>roads[i] = [ui, vi, timei]</code> means that there is a road between intersections <code>ui</code> and <code>vi</code> that takes <code>timei</code> minutes to travel. You want to know in how many ways you can travel from intersection <code>0</code> to intersection <code>n - 1</code> in the shortest amount of time.

Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2025/02/14/1976_corrected.png" style="width: 255px; height: 400px;" />
<pre>
Input: n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Output: 4
Explanation: The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
</pre>

Example 2:

<pre>
Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 200</code></li>
	<li><code>n - 1 &lt;= roads.length &lt;= n * (n - 1) / 2</code></li>
	<li><code>roads[i].length == 3</code></li>
	<li><code>0 &lt;= ui, vi &lt;= n - 1</code></li>
	<li><code>1 &lt;= timei &lt;= 109</code></li>
	<li><code>ui != vi</code></li>
	<li>There is at most one road connecting any two intersections.</li>
	<li>You can reach any intersection from any other intersection.</li>
</ul>

countPaths

Number of Ways to Arrive at Destination

All Paths From Source to Target

all-paths-from-source-to-target

所有可能的路径

Path with Maximum Probability

path-with-maximum-probability

概率最大的路径

Second Minimum Time to Reach Destination

second-minimum-time-to-reach-destination

到达目的地的第二短时间

Graph

Topological Sort

Dynamic Programming

Shortest Path

你在一个城市里，城市由 <code>n</code>&nbsp;个路口组成，路口编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;，某些路口之间有 双向&nbsp;道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。

给你一个整数&nbsp;<code>n</code>&nbsp;和二维整数数组&nbsp;<code>roads</code>&nbsp;，其中&nbsp;<code>roads[i] = [ui, vi, timei]</code>&nbsp;表示在路口&nbsp;<code>ui</code>&nbsp;和&nbsp;<code>vi</code>&nbsp;之间有一条需要花费&nbsp;<code>timei</code>&nbsp;时间才能通过的道路。你想知道花费 最少时间&nbsp;从路口&nbsp;<code>0</code>&nbsp;出发到达路口&nbsp;<code>n - 1</code>&nbsp;的方案数。

请返回花费 最少时间&nbsp;到达目的地的 路径数目&nbsp;。由于答案可能很大，将结果对&nbsp;<code>109 + 7</code>&nbsp;取余&nbsp;后返回。

&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2025/02/14/1976_corrected.png" style="width: 255px; height: 400px;" />
<pre>
输入：n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
输出：4
解释：从路口 0 出发到路口 6 花费的最少时间是 7 分钟。
四条花费 7 分钟的路径分别为：
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
</pre>

示例 2：

<pre>
输入：n = 2, roads = [[1,0,10]]
输出：1
解释：只有一条从路口 0 到路口 1 的路，花费 10 分钟。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 200</code></li>
	<li><code>n - 1 &lt;= roads.length &lt;= n * (n - 1) / 2</code></li>
	<li><code>roads[i].length == 3</code></li>
	<li><code>0 &lt;= ui, vi &lt;= n - 1</code></li>
	<li><code>1 &lt;= timei &lt;= 109</code></li>
	<li><code>ui != vi</code></li>
	<li>任意两个路口之间至多有一条路。</li>
	<li>从任意路口出发，你能够到达其他任意路口。</li>
</ul>