算法-交替方向的最小路径代价III-Dijkstra最短路径算法

题目给你两个整数m和n表示一个网格的行数和列数。你的目标是到达单元格(m - 1, n - 1)。同时给你一个二维整数数组penalty。进入单元格(i, j)的代价为(i 1) * (j 1)。你从单元格(0, 0)开始最初需要支付其入口代价。进入(0, 0)后执行的行动从 1 开始编号。在每次行动中你可以移动到一个相邻的单元格或者在当前单元格等待。如果满足以下条件则移动遵循奇偶性规则在奇数编号的行动中你向右或向下移动。在偶数编号的行动中你向左或向上移动。行动的代价由以下方式决定如果你遵循奇偶性规则移动只需支付目标单元格的入口代价。如果你在违反奇偶性规则的方向上移动支付目标单元格的入口代价加上penalty[i][j]其中(i, j)是你移动前所在的单元格。如果你在单元格(i, j)中等待支付penalty[i][j]。在每次移动或等待之后行动编号增加 1。因此无论是否支付了惩罚代价所需遵循的奇偶性规则在每次行动后都会交替改变。返回到达(m - 1, n - 1)所需的最小总代价。示例 1输入m 2, n 2, penalty [[5,3],[1,4]]输出8解释最优路径为从单元格(0, 0)开始入口代价为(0 1) * (0 1) 1。行动 1向下移动到单元格(1, 0)入口代价为(1 1) * (0 1) 2。行动 2向右移动到单元格(1, 1)入口代价为(1 1) * (1 1) 4因为违反了偶数奇偶性规则额外代价为penalty[1][0] 1。因此总代价为1 2 4 1 8。题解思路Dijkstra最短路径算法模版题需要注意的是除了优先级队列还需要一个最小值数组维护答案举例比如从A出发到C有两条路径A-C是权值是5先A-B,全值是3然后B-C,权值是4按优先级队列会先走A-B再走B-C权值和是7但实际上是从A-C权值是5权值最小这就需要一个最小值数组另外需要考虑的就是最小值数组维护的维度。class Solution { // 奇数下标 1,3 对应向右或向下 // 偶数下标 0,2 对应向左或向上 private static final int[][] DIRS {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下 private record Node(long d, int i, int j, int k) { } public long minCost(int m, int n, int[][] penalty) { long[][][] dis new long[m][n][2]; for (long[][] mat : dis) { for (long[] row : mat) { Arrays.fill(row, Long.MAX_VALUE); } } PriorityQueueNode pq new PriorityQueue((a, b) - Long.compare(a.d, b.d)); // 支付 1 的入口代价 dis[0][0][1] 1; pq.offer(new Node(1, 0, 0, 1)); while (true) { Node top pq.poll(); long d top.d; int i top.i; int j top.j; int k top.k; if (i m - 1 j n - 1) { return d; } if (d dis[i][j][k]) { continue; } int p penalty[i][j]; // 原地不动 long newDis d p; if (newDis dis[i][j][k ^ 1]) { dis[i][j][k ^ 1] newDis; pq.offer(new Node(newDis, i, j, k ^ 1)); // k^1 切换行动编号的奇偶性 } // 移动一步 for (int idx 0; idx 4; idx) { int x i DIRS[idx][0]; int y j DIRS[idx][1]; if (0 x x m 0 y y n) { // 如果 k 和 idx 的奇偶性不同那么违反了奇偶性规则需要额外支付 p 的代价 newDis d (x 1) * (y 1) (idx % 2 ^ k) * p; if (newDis dis[x][y][k ^ 1]) { dis[x][y][k ^ 1] newDis; pq.offer(new Node(newDis, x, y, k ^ 1)); // k^1 切换行动编号的奇偶性 } } } } } }