Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Number of Ways to Arrive at Destination
Bookmark
Input
Standard
Small
Diamond
Custom
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]]
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
heap
dist
0
0
1
∞
2
∞
3
∞
4
∞
5
∞
6
∞
ways
0
1
1
0
2
0
3
0
4
0
5
0
6
0
ways[6] = 0
count the shortest paths from
0
to
6
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
heap
dist
0
0
1
∞
2
∞
3
∞
4
∞
5
∞
6
∞
ways
0
1
1
0
2
0
3
0
4
0
5
0
6
0
ways[6] = 0
count the shortest paths from
0
to
6
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
heap
dist
0
0
1
∞
2
∞
3
∞
4
∞
5
∞
6
7
ways
0
1
1
0
2
0
3
0
4
0
5
0
6
1
ways[6] = 1
shorter → dist[
6
] =
7
, ways[
6
] = ways[
0
] =
1
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
heap
2·1
min
7·6
dist
0
0
1
2
2
∞
3
∞
4
∞
5
∞
6
7
ways
0
1
1
1
2
0
3
0
4
0
5
0
6
1
ways[6] = 1
edge
0→4
(
5
):
0 + 5 = 5
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
heap
5·4
min
7·6
dist
0
0
1
2
2
∞
3
∞
4
5
5
∞
6
7
ways
0
1
1
1
2
0
3
0
4
1
5
0
6
1
ways[6] = 1
edge
1→2
(
3
):
2 + 3 = 5
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
heap
5·4
min
5·2
5·3
7·6
dist
0
0
1
2
2
5
3
5
4
5
5
∞
6
7
ways
0
1
1
1
2
1
3
1
4
1
5
0
6
1
ways[6] = 1
push
(, node 3)
into the heap
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
heap
5·3
min
7·6
dist
0
0
1
2
2
5
3
5
4
5
5
∞
6
7
ways
0
1
1
1
2
1
3
1
4
1
5
0
6
2
ways[6] = 2
pop node
2
at dist
5
— settle it
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
heap
6·5
min
7·6
dist
0
0
1
2
2
5
3
5
4
5
5
6
6
7
ways
0
1
1
1
2
1
3
1
4
1
5
1
6
2
ways[6] = 2
pop node
3
at dist
5
— settle it
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
heap
7·6
min
dist
0
0
1
2
2
5
3
5
4
5
5
6
6
7
ways
0
1
1
1
2
1
3
1
4
1
5
2
6
2
ways[6] = 2
pop node
5
at dist
6
— settle it
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
heap
dist
0
0
1
2
2
5
3
5
4
5
5
6
6
7
ways
0
1
1
1
2
1
3
1
4
1
5
2
6
4
ways[6] = 4
pop node
6
at dist
7
— settle it
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
heap
dist
0
0
1
2
2
5
3
5
4
5
5
6
6
7
ways
0
1
1
1
2
1
3
1
4
1
5
2
6
4
ways[6] = 4
ways[6] = 4 shortest paths
algo
master
.
io
Step:
Count the shortest paths from node 0 to node 6
0 / 45
Input
Standard
Small
Diamond
Custom
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]]
0 / 45
algo
master
.
io
Step:
Count the shortest paths from node 0 to node 6
