算法：暴力最短路 $dijkstra$

先用哈希表把每个值和下标建立映射，然后把每个坐标都转换到 $x \times m + y$，相当于看成一个个点，然后利用 $moveCost$ 数组建图，建完后对第一行的每个点都当源点都跑一遍最短路即可，虽然代码量大，时间空间效率低，但是它非常滴套路（喜）

本来稠密图适合朴素版的来着，但是写习惯了堆优化的了（）

时间复杂度 $O(m \times cn \times cm \times log(n \times m))$

• 常数巨大（悲）

C++ 代码

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 2600, M = 2000010, INF = 0x3f3f3f3f;

class Solution {
public:
    int n, m;
    int h[N], e[M], w[M], ne[M], idx;
    vector<vector<int>> g;
    int d[N];
    bool st[N];

    void add(int a, int b, int c) {
        e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    }

    int get(PII t) {
        return t.x * m + t.y;
    }

    int dijk(int x, int y) {
        memset(st, 0, sizeof st);
        memset(d, 0x3f, sizeof d);
        int s = get({x, y});
        d[s] = g[x][y];

        priority_queue<PII, vector<PII>, greater<PII>> heap;
        heap.push({d[s], s});

        while (heap.size()) {
            auto t = heap.top().y; heap.pop();
            if (st[t]) continue;
            st[t] = true;
            for (int i = h[t]; ~i; i = ne[i]) {
                int j = e[i];
                if (d[j] > d[t] + w[i] + g[j / m][j % m]) {
                    d[j] = d[t] + w[i] + g[j / m][j % m];
                    heap.push({d[j], j});
                }
            }
        }
        int res = 2e9;
        for (int i = 0; i < m; i ++ ) res = min(res, d[get({n - 1, i})]);
        return res;
    }

    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& c) {
        g = grid;
        n = g.size(), m = g[0].size();
        unordered_map<int, PII> hash;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                hash[g[i][j]] = {i, j};

        memset(h, -1, sizeof h);
        int cn = c.size(), cm = c[0].size();
        for (int i = 0; i < cn; i ++ )
            if (hash[i].x + 1 < n)
                for (int j = 0; j < cm; j ++ )
                    add(get(hash[i]), get({hash[i].x + 1, j}), c[i][j]);

        int res = 2e9;
        for (int i = 0; i < m; i ++ ) res = min(res, dijk(0, i));
        return res;
    }
};

一时兴起，就是如果实在想不到用 $DP$ 的话，不妨试试上面那个，这题 $dp$ 写起来也很快的

• 状态转移方程 $f(i, j) = f(i - 1, k) + cost(g[i - 1][k], j) + g[i][j]$

• 时间复杂度 $O(nm^2)$

class Solution {
public:
    int minPathCost(vector<vector<int>>& g, vector<vector<int>>& c) {
        int n = g.size(), m = g[0].size();
        vector<vector<int>> f(n, vector<int>(m, (int)2e9));
        for (int i = 0; i < m; i ++ ) f[0][i] = g[0][i];
        for (int i = 1; i < n; i ++ )
            for (int j = 0; j < m; j ++ )  
                for (int k = 0; k < m; k ++ )
                    f[i][j] = min(f[i][j], f[i - 1][k] + c[g[i - 1][k]][j] + g[i][j]);

        int res = 2e9;
        for (int i = 0; i < m; i ++ ) res = min(res, f[n - 1][i]);
        return res;
    }
};