题解 | #最小体重积# 最短路 Dijkstra

知识点

最短路 Dijkstra

思路

这道题要求可以上下左右四个方向移动，那么需要用Dijkstra算法，如果只允许向下或者向右移动，那么可以用DP解决。

DP在当前的题面中是错误的。

hack数据：

[[1,1,1,9],[9,9,1,9],[9,1,1,9],[9,1,9,9],[9,1,1,1]]

这个数据长这样, 明显存在一条为1的最短路，DP无法得到这个解

1 1 1 9

9 9 1 9

9 1 1 9

9 1 9 9

9 1 1 1

我认为正解是dijkstra，每一次可以向周围的四个格子移动。n为点数, m是边数, 由于只能向周围四个方向移动, m = 4n, 所以时间复杂度为

AC Code (C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型vector<vector<>> 
     * @return long长整型
     */
    using ll = long long;
    using al3 = array<ll, 3>;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, -1, 0, 1};
    ll dist[35][35];
    bool st[35][35];
    int n, m;
    long long minPathProduct(vector<vector<int> >& cows) {
        // dijkstra
        n = cows.size(), m = cows[0].size();
        return dijkstra(cows);
    }
    ll dijkstra(vector<vector<int> >& val) {
        memset(dist, 0x3f, sizeof dist);
        memset(st, 0, sizeof st);
        dist[0][0] = val[0][0];
        priority_queue<al3, vector<al3>, greater<>> heap;
        heap.push({val[0][0], 0, 0});

        while (heap.size()) {
            auto [distance, x, y] = heap.top();
            heap.pop();

            if (st[x][y]) continue;
            st[x][y] = true;

            for (int i = 0; i < 4; i ++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 or ny < 0 or nx >= n or ny >= m) continue;
                if (dist[nx][ny] > distance * val[nx][ny]) {
                    dist[nx][ny] = distance * val[nx][ny];
                    heap.push({dist[nx][ny], nx, ny});
                }
            }
        }
        return dist[n - 1][m - 1];
    }
};

// 1 1 1 9
// 9 9 1 9
// 9 1 1 9
// 9 1 9 9
// 9 1 1 1

// [[1,1,1,9],[9,9,1,9],[9,1,1,9],[9,1,9,9],[9,1,1,1]]