3651. Minimum Cost Path with Teleportations

Approach

Dijkstra on grid with normal moves costing 1 and teleportation edges costing 0.

Key Techniques

Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.

Graph

Graph algorithms model relationships between entities. Core algorithms: DFS/BFS for traversal, Dijkstra for weighted shortest path, Bellman-Ford for negative weights, Floyd-Warshall for all-pairs, and Kruskal/Prim for minimum spanning trees. Represent graphs as adjacency lists (Dictionary<int, List<int>>) for efficiency.

Shortest Path

Shortest path algorithms find minimum-cost routes in graphs. Dijkstra (non-negative weights, O((V+E) log V)), Bellman-Ford (negative edges, O(VE)), Floyd-Warshall (all-pairs, O(V³)), and BFS (unweighted, O(V+E)). In C#, use PriorityQueue for Dijkstra.

3651.cs

// Approach: Dijkstra on grid with normal moves costing 1 and teleportation edges costing 0.
// Time: O(mn log(mn)) Space: O(mn)

public class Solution
{
    public int MinCost(int[][] grid, int k)
    {
        int m = grid.Length, n = grid[0].Length;
        int inf = int.MaxValue / 2;

        int[,,] f = new int[k + 1, m, n];
        for (int t = 0; t <= k; t++)
        {
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                    f[t, i, j] = inf;
            }
        }

        f[0, 0, 0] = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i > 0)
                    f[0, i, j] = Math.Min(f[0, i, j], f[0, i - 1, j] + grid[i][j]);
                if (j > 0)
                    f[0, i, j] = Math.Min(f[0, i, j], f[0, i, j - 1] + grid[i][j]);
            }
        }

        var g = new Dictionary<int, List<(int, int)>>();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int x = grid[i][j];
                if (!g.ContainsKey(x))
                    g[x] = new List<(int, int)>();
                g[x].Add((i, j));
            }
        }

        var keys = g.Keys.ToList();
        keys.Sort((a, b) => b.CompareTo(a)); // reverse order

        for (int t = 1; t <= k; t++)
        {
            int mn = inf;
            foreach (int key in keys)
            {
                var pos = g[key];
                foreach (var p in pos)
                    mn = Math.Min(mn, f[t - 1, p.Item1, p.Item2]);
                foreach (var p in pos)
                    f[t, p.Item1, p.Item2] = mn;
            }
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (i > 0)
                        f[t, i, j] = Math.Min(f[t, i, j], f[t, i - 1, j] + grid[i][j]);
                    if (j > 0)
                        f[t, i, j] = Math.Min(f[t, i, j], f[t, i, j - 1] + grid[i][j]);
                }
            }
        }

        int ans = inf;
        for (int t = 0; t <= k; t++)
            ans = Math.Min(ans, f[t, m - 1, n - 1]);

        return ans;
    }
}

Was this solution helpful?