We need to find the cheapest path from the top-left to the bottom-right of a grid, where we can only move right or down (paying the destination cell's value), but we also have up to k free "teleportation" jumps. A teleportation lets us instantly move to any cell whose value is less than or equal to our current cell's value, at zero cost.

The normal movement part is a standard grid DP problem. The teleportation is what makes this hard. A single teleport can move you across the entire grid at zero cost, but only to a cell with an equal or smaller value. Teleportations are most useful when you are standing on a high-value cell, because more destinations become reachable. The best teleport targets are low-value cells close to the bottom-right corner, since fewer expensive normal moves remain afterward.

Teleportations split the problem into layers. With zero teleportations, it is standard DP. Each teleportation lets you restart from a new position at no cost, as long as the destination value does not exceed the cell you teleport from. So the problem is k+1 phases of normal movement, separated by up to k teleportation jumps.

Key Constraints:

Intuition

Model this as a shortest path problem. Each state is a triple (row, col, teleports_remaining), and Dijkstra's algorithm finds the minimum cost from (0, 0, k) to (m-1, n-1, *). All edge weights are non-negative (normal moves cost a cell value >= 0, teleports cost 0), so Dijkstra applies.

From any state (i, j, t), we have two types of transitions:

The teleportation edges are the expensive part. From each cell, a teleport can reach up to mn other cells, so each pop can push up to O(mn) entries onto the priority queue.

Algorithm

Example Walkthrough

Code

The bottleneck is teleportation. For every state popped from the heap, the algorithm scans all mn cells for valid targets. The next approach removes that cost by processing all teleportations for a whole phase in one sorted sweep, dropping the time to O(mnlog(mn) + kmn).

Intuition

Instead of treating each teleportation as an individual graph edge, process the problem in phases. Phase 0 has zero teleportations and runs standard right-down DP. Phase 1 takes the phase 0 results, applies one teleportation, then runs another right-down DP pass. This repeats for up to k phases.

After computing DP for phase t, we need an efficient way to find where teleportation can take us in phase t+1. To teleport into cell (x, y), we must come from a cell (a, b) where grid[a][b] >= grid[x][y]. The cost of arriving at (x, y) by teleport is the minimum dp[t][a][b] over all such cells. So for each destination cell, we want the smallest DP value among all cells whose grid value is at least the destination's value.

Sorting solves this in one pass. Sort all cells by grid value in descending order and keep a running minimum of DP costs while iterating. When the scan reaches a cell with value v, every cell seen so far has value >= v, so the running minimum is the cheapest teleport source for that cell.

One detail matters. Cells with the same grid value can teleport to each other, because the condition is <=, not <. So all cells of one value must be processed as a group: first update the running minimum with every DP value in the group, then assign that running minimum as the teleport cost to every cell in the group. Doing it in two passes lets equal-valued cells serve as sources for each other.

Algorithm

Example Walkthrough

Code