Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Minimum Cost Path with Teleportations
Bookmark
State Dijkstra
Layered DP
Input
Example 1
Example 2 (k=2)
Small 2x2
3x4 Grid
No Teleport (k=0)
Custom
grid
=
[[1,2,3],[4,5,1],[1,2,1]]
,
k
=
1
grid
1
2
3
4
5
1
1
2
1
heap (cost, row, col, teleports left)
grid
1
2
3
4
5
1
1
2
1
heap (cost, row, col, teleports left)
grid
1
2
3
4
5
1
1
2
1
best cost per cell
0
∞
∞
∞
∞
∞
∞
∞
∞
dist[r][c][t] = best cost with t teleports left
heap (cost, row, col, teleports left)
grid
1
2
3
4
5
1
1
2
1
best cost per cell
0
∞
∞
∞
∞
∞
∞
∞
∞
pop (0,0) at cost 0 with 1 teleport(s) left
heap (cost, row, col, teleports left)
grid
1
2
3
4
5
1
1
2
1
best cost per cell
0
2
∞
4
∞
0
0
∞
0
teleport free to any cell of value <= 1
heap (cost, row, col, teleports left)
0@0,0|0
0@1,2|0
0@2,0|0
0@2,2|0
2@0,1|1
4@1,0|1
grid
1
2
3
4
5
1
1
2
1
best cost per cell
0
2
∞
4
∞
0
0
∞
0
(0,0) -> (1,0) costs 0 + 4 = 4
heap (cost, row, col, teleports left)
0@1,2|0
0@2,0|0
0@2,2|0
2@0,1|1
4@1,0|1
4@1,0|0
grid
1
2
3
4
5
1
1
2
1
best cost per cell
0
2
∞
4
∞
0
0
∞
0
no teleports left
heap (cost, row, col, teleports left)
0@1,2|0
0@2,0|0
0@2,2|0
2@0,1|1
2@0,1|0
4@1,0|1
4@1,0|0
grid
1
2
3
4
5
1
1
2
1
best cost per cell
0
2
∞
4
∞
0
0
∞
0
(1,2) -> (2,2) costs 0 + 1 = 1
heap (cost, row, col, teleports left)
0@2,0|0
0@2,2|0
2@0,1|1
2@0,1|0
4@1,0|1
4@1,0|0
grid
1
2
3
4
5
1
1
2
1
best cost per cell
0
2
∞
4
∞
0
0
2
0
(2,0) -> (2,1) costs 0 + 2 = 2
heap (cost, row, col, teleports left)
0@2,2|0
2@0,1|1
2@0,1|0
2@2,1|0
4@1,0|1
4@1,0|0
grid
1
2
3
4
5
1
1
2
1
best cost per cell
0
2
∞
4
∞
0
0
2
0
pop (2,2) at cost 0 with 0 teleport(s) left
heap (cost, row, col, teleports left)
2@0,1|1
2@0,1|0
2@2,1|0
4@1,0|1
4@1,0|0
grid
1
2
3
4
5
1
1
2
1
best cost per cell
0
2
∞
4
∞
0
0
2
0
minimum cost = 0
heap (cost, row, col, teleports left)
2@0,1|1
2@0,1|0
2@2,1|0
4@1,0|1
4@1,0|0
algo
master
.
io
Step:
Starting Minimum Cost Path with Teleportations
0 / 20
Input
Example 1
Example 2 (k=2)
Small 2x2
3x4 Grid
No Teleport (k=0)
Custom
grid
=
[[1,2,3],[4,5,1],[1,2,1]]
,
k
=
1
0 / 20
algo
master
.
io
Step:
Starting Minimum Cost Path with Teleportations
