Move from brute-force thinking to an efficient approach using dynamic programming strategy.
You are in a city that consists of n intersections numbered from 0 to n - 1 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 n and a 2D integer array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n - 1 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 109 + 7.
Example 1:
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
Example 2:
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.
Constraints:
1 <= n <= 200n - 1 <= roads.length <= n * (n - 1) / 2roads[i].length == 30 <= ui, vi <= n - 11 <= timei <= 109ui != viProblem summary: You are in a city that consists of n intersections numbered from 0 to n - 1 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 n and a 2D integer array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n - 1 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 109 + 7.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Dynamic Programming · Topological Sort
7 [[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]]
2 [[1,0,10]]
all-paths-from-source-to-target)path-with-maximum-probability)second-minimum-time-to-reach-destination)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1976: Number of Ways to Arrive at Destination
class Solution {
public int countPaths(int n, int[][] roads) {
final long inf = Long.MAX_VALUE / 2;
final int mod = (int) 1e9 + 7;
long[][] g = new long[n][n];
for (var e : g) {
Arrays.fill(e, inf);
}
for (var r : roads) {
int u = r[0], v = r[1], t = r[2];
g[u][v] = t;
g[v][u] = t;
}
g[0][0] = 0;
long[] dist = new long[n];
Arrays.fill(dist, inf);
dist[0] = 0;
long[] f = new long[n];
f[0] = 1;
boolean[] vis = new boolean[n];
for (int i = 0; i < n; ++i) {
int t = -1;
for (int j = 0; j < n; ++j) {
if (!vis[j] && (t == -1 || dist[j] < dist[t])) {
t = j;
}
}
vis[t] = true;
for (int j = 0; j < n; ++j) {
if (j == t) {
continue;
}
long ne = dist[t] + g[t][j];
if (dist[j] > ne) {
dist[j] = ne;
f[j] = f[t];
} else if (dist[j] == ne) {
f[j] = (f[j] + f[t]) % mod;
}
}
}
return (int) f[n - 1];
}
}
// Accepted solution for LeetCode #1976: Number of Ways to Arrive at Destination
func countPaths(n int, roads [][]int) int {
const inf = math.MaxInt64 / 2
const mod = int(1e9 + 7)
g := make([][]int, n)
dist := make([]int, n)
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = inf
dist[i] = inf
}
}
for _, r := range roads {
u, v, t := r[0], r[1], r[2]
g[u][v] = t
g[v][u] = t
}
f := make([]int, n)
vis := make([]bool, n)
f[0] = 1
g[0][0] = 0
dist[0] = 0
for i := 0; i < n; i++ {
t := -1
for j := 0; j < n; j++ {
if !vis[j] && (t == -1 || dist[j] < dist[t]) {
t = j
}
}
vis[t] = true
for j := 0; j < n; j++ {
if j == t {
continue
}
ne := dist[t] + g[t][j]
if dist[j] > ne {
dist[j] = ne
f[j] = f[t]
} else if dist[j] == ne {
f[j] = (f[j] + f[t]) % mod
}
}
}
return f[n-1]
}
# Accepted solution for LeetCode #1976: Number of Ways to Arrive at Destination
class Solution:
def countPaths(self, n: int, roads: List[List[int]]) -> int:
g = [[inf] * n for _ in range(n)]
for u, v, t in roads:
g[u][v] = g[v][u] = t
g[0][0] = 0
dist = [inf] * n
dist[0] = 0
f = [0] * n
f[0] = 1
vis = [False] * n
for _ in range(n):
t = -1
for j in range(n):
if not vis[j] and (t == -1 or dist[j] < dist[t]):
t = j
vis[t] = True
for j in range(n):
if j == t:
continue
ne = dist[t] + g[t][j]
if dist[j] > ne:
dist[j] = ne
f[j] = f[t]
elif dist[j] == ne:
f[j] += f[t]
mod = 10**9 + 7
return f[-1] % mod
// Accepted solution for LeetCode #1976: Number of Ways to Arrive at Destination
/**
* [1976] Number of Ways to Arrive at Destination
*
* You are in a city that consists of n intersections numbered from 0 to n - 1 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 n and a 2D integer array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n - 1 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 10^9 + 7.
*
* Example 1:
* <img alt="" src="https://assets.leetcode.com/uploads/2025/02/14/1976_corrected.png" style="width: 255px; height: 400px;" />
* 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
*
* Example 2:
*
* 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.
*
*
* Constraints:
*
* 1 <= n <= 200
* n - 1 <= roads.length <= n * (n - 1) / 2
* roads[i].length == 3
* 0 <= ui, vi <= n - 1
* 1 <= timei <= 10^9
* ui != vi
* There is at most one road connecting any two intersections.
* You can reach any intersection from any other intersection.
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/
// discuss: https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
impl Solution {
pub fn count_paths(n: i32, roads: Vec<Vec<i32>>) -> i32 {
0
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
#[ignore]
fn test_1976_example_1() {
let n = 7;
let roads = vec![
vec![0, 6, 7],
vec![0, 1, 2],
vec![1, 2, 3],
vec![1, 3, 3],
vec![6, 3, 3],
vec![3, 5, 1],
vec![6, 5, 1],
vec![2, 5, 1],
vec![0, 4, 5],
vec![4, 6, 2],
];
let result = 4;
assert_eq!(Solution::count_paths(n, roads), result);
}
#[test]
#[ignore]
fn test_1976_example_2() {
let n = 2;
let roads = vec![vec![1, 0, 10]];
let result = 1;
assert_eq!(Solution::count_paths(n, roads), result);
}
}
// Accepted solution for LeetCode #1976: Number of Ways to Arrive at Destination
function countPaths(n: number, roads: number[][]): number {
const mod: number = 1e9 + 7;
const g: number[][] = Array.from({ length: n }, () => Array(n).fill(Infinity));
for (const [u, v, t] of roads) {
g[u][v] = t;
g[v][u] = t;
}
g[0][0] = 0;
const dist: number[] = Array(n).fill(Infinity);
dist[0] = 0;
const f: number[] = Array(n).fill(0);
f[0] = 1;
const vis: boolean[] = Array(n).fill(false);
for (let i = 0; i < n; ++i) {
let t: number = -1;
for (let j = 0; j < n; ++j) {
if (!vis[j] && (t === -1 || dist[j] < dist[t])) {
t = j;
}
}
vis[t] = true;
for (let j = 0; j < n; ++j) {
if (j === t) {
continue;
}
const ne: number = dist[t] + g[t][j];
if (dist[j] > ne) {
dist[j] = ne;
f[j] = f[t];
} else if (dist[j] === ne) {
f[j] = (f[j] + f[t]) % mod;
}
}
}
return f[n - 1];
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.