具體的，我們創(chuàng)建一個(gè)“虛擬源點(diǎn)”，該點(diǎn)向所有第一行的點(diǎn)連權(quán)值為 的有向邊；同時(shí)創(chuàng)建一個(gè)“虛擬匯點(diǎn)”，最后一行的所有點(diǎn)向該點(diǎn)連權(quán)值為 的有向邊。

問(wèn)題進(jìn)一步轉(zhuǎn)化為：求“虛擬源點(diǎn)”到“虛擬匯點(diǎn)”的最短路。

至此，我們通過(guò) 「建新圖 -> 創(chuàng)建虛擬源匯點(diǎn)（轉(zhuǎn)換為單源最短路）-> 套用單源最短路算法」 解決本題。

將新圖中點(diǎn)的數(shù)量記為 ，邊數(shù)記為 ，樸素 Dijkstra 復(fù)雜度為 ，堆優(yōu)化的 Dijkstra 的復(fù)雜度為 ，當(dāng) （相對(duì)稀疏）時(shí)，優(yōu)先使用堆優(yōu)化 Dijkstra。

Java 代碼：

class?Solution?{
????int?N?=?50?*?50?+?2,?M?=?50?*?50?*?50,?idx?=?0,?n;
????int[]?he?=?new?int[N],?e?=?new?int[M],?ne?=?new?int[M],?w?=?new?int[M];
????void?add(int?a,?int?b,?int?c)?{
????????e[idx]?=?b;
????????ne[idx]?=?he[a];
????????w[idx]?=?c;
????????he[a]?=?idx++;
????}
????public?int?minPathCost(int[][]?grid,?int[][]?moveCost)?{
????????int?N?=?grid.length,?M?=?grid[0].length;
????????int?S?=?N?*?M,?T?=?S?+?1;
????????n?=?N?*?M?+?2;
????????Arrays.fill(he,?-1);
????????//「虛擬源點(diǎn)」向「第一行」進(jìn)行連邊
????????for?(int?i?=?0;?i?<?M;?i++)?add(S,?grid[0][i],?grid[0][i]);
????????//?轉(zhuǎn)換原圖
????????for?(int?i?=?0;?i?<?N?-?1;?i++)?{
????????????for?(int?j?=?0;?j?<?M;?j++)?{
????????????????int?a?=?grid[i][j];
????????????????for?(int?k?=?0;?k?<?M;?k++)?{
????????????????????int?b?=?grid[i?+?1][k];
????????????????????add(a,?b,?moveCost[a][k]?+?b);
????????????????}
????????????}
????????}
????????//「最后一行」向「虛擬匯點(diǎn)」進(jìn)行連邊
????????for?(int?i?=?0;?i?<?M;?i++)?add(grid[N?-?1][i],?T,?0);
????????//?最短路
????????int[]?dist?=?dijkstra(S);
????????return?dist[T];
????}
????int[]?dijkstra(int?x)?{
????????//?起始先將所有的點(diǎn)標(biāo)記為「未更新」和「距離為正無(wú)窮」
????????int[]?dist?=?new?int[n];
????????Arrays.fill(dist,?0x3f3f3f3f);
????????boolean[]?vis?=?new?boolean[n];
????????dist[x]?=?0;
????????//?使用「優(yōu)先隊(duì)列」存儲(chǔ)所有可用于更新的點(diǎn)
????????//?以?(點(diǎn)編號(hào),?到起點(diǎn)的距離)?進(jìn)行存儲(chǔ)，優(yōu)先彈出「最短距離」較小的點(diǎn)
????????PriorityQueue<int[]>?q?=?new?PriorityQueue<>((a,b)->a[1]-b[1]);
????????q.add(new?int[]{x,?0});
????????while?(!q.isEmpty())?{
????????????//?每次從「優(yōu)先隊(duì)列」中彈出
????????????int[]?poll?=?q.poll();
????????????int?u?=?poll[0],?step?=?poll[1];
????????????//?如果彈出的點(diǎn)被標(biāo)記「已更新」，則跳過(guò)
????????????if?(vis[u])?continue;
????????????//?標(biāo)記該點(diǎn)「已更新」，并使用該點(diǎn)更新其他點(diǎn)的「最短距離」
????????????vis[u]?=?true;
????????????for?(int?i?=?he[u];?i?!=?-1;?i?=?ne[i])?{
????????????????int?j?=?e[i];
????????????????if?(dist[j]?<=?dist[u]?+?w[i])?continue;
????????????????dist[j]?=?dist[u]?+?w[i];
????????????????q.add(new?int[]{j,?dist[j]});
????????????}
????????}
????????return?dist;
????}
}

C++ 代碼：

class?Solution?{
public:
????static?const?int?N?=?50?*?50?+?2,?M?=?50?*?50?*?50;
????int?he[N],?e[M],?ne[M],?w[M],?idx,?n,?INF?=?0x3f3f3f3f;
????void?add(int?a,?int?b,?int?c)?{
????????e[idx]?=?b;
????????ne[idx]?=?he[a];
????????w[idx]?=?c;
????????he[a]?=?idx++;
????}
????int?minPathCost(vector<vector<int>>&?grid,?vector<vector<int>>&?moveCost)?{
????????int?N?=?grid.size(),?M?=?grid[0].size();
????????int?S?=?N?*?M,?T?=?S?+?1;
????????n?=?N?*?M?+?2;
????????fill(he,?he?+?n,?-1);
????????//「虛擬源點(diǎn)」向「第一行」進(jìn)行連邊
????????for?(int?i?=?0;?i?<?M;?i++)?add(S,?grid[0][i],?grid[0][i]);
????????//?轉(zhuǎn)換原圖
????????for?(int?i?=?0;?i?<?N?-?1;?i++)?{
????????????for?(int?j?=?0;?j?<?M;?j++)?{
????????????????int?a?=?grid[i][j];
????????????????for?(int?k?=?0;?k?<?M;?k++)?{
????????????????????int?b?=?grid[i?+?1][k];
????????????????????add(a,?b,?moveCost[a][k]?+?b);
????????????????}
????????????}
????????}
????????//「最后一行」向「虛擬匯點(diǎn)」進(jìn)行連邊
????????for?(int?i?=?0;?i?<?M;?i++)?add(grid[N?-?1][i],?T,?0);
????????//?最短路
????????vector<int>?dist?=?dijkstra(S);
????????return?dist[T];
????}
????vector<int>?dijkstra(int?x)?{
????????vector<int>?dist(n,?0x3f3f3f3f);
????????vector<bool>?vis(n,?false);
????????dist[x]?=?0;
????????//?使用「優(yōu)先隊(duì)列」存儲(chǔ)所有可用于更新的點(diǎn)
????????//?以?(到起點(diǎn)的距離,?點(diǎn)編號(hào))?進(jìn)行存儲(chǔ)，優(yōu)先彈出「最短距離」較小的點(diǎn)
????????priority_queue<pair<int,?int>,?vector<pair<int,?int>>,?greater<pair<int,?int>>>?q;
????????q.push({0,?x});
????????while?(!q.empty())?{
????????????//?每次從「優(yōu)先隊(duì)列」中彈出
????????????auto?[step,?u]?=?q.top();
????????????q.pop();
????????????//?如果彈出的點(diǎn)被標(biāo)記「已更新」，則跳過(guò)
????????????if?(vis[u])?continue;
????????????//?標(biāo)記該點(diǎn)「已更新」，并使用該點(diǎn)更新其他點(diǎn)的「最短距離」
????????????vis[u]?=?true;
????????????for?(int?i?=?he[u];?i?!=?-1;?i?=?ne[i])?{
????????????????int?j?=?e[i];
????????????????if?(dist[j]?<=?dist[u]?+?w[i])?continue;
????????????????dist[j]?=?dist[u]?+?w[i];
????????????????q.push({dist[j],?j});
????????????}
????????}
????????return?dist;
????}
};

Python 代碼：

import?heapq

class?Solution:
????def?minPathCost(self,?grid,?moveCost):
????????N,?M?=?len(grid),?len(grid[0])
????????S,?T?=?N?*?M,?N?*?M?+?1
????????n?=?N?*?M?+?2
????????he?=?[-1]?*?n
????????e,?ne,?w?=?[-1]?*?(50?*?50?*?50),?[-1]?*?(50?*?50?*?50),?[-1]?*?(50?*?50?*?50)
????????idx?=?0

????????def?add(a,?b,?c):
????????????nonlocal?idx
????????????e[idx]?=?b
????????????ne[idx]?=?he[a]
????????????w[idx]?=?c
????????????he[a]?=?idx
????????????idx?+=?1

????????def?dijkstra(x):
????????????dist?=?[float('inf')]?*?n
????????????vis?=?[False]?*?n
????????????dist[x]?=?0
????????????#?使用「優(yōu)先隊(duì)列」存儲(chǔ)所有可用于更新的點(diǎn)
????????????#?以?(到起點(diǎn)的距離,?點(diǎn)編號(hào))?進(jìn)行存儲(chǔ)，優(yōu)先彈出「最短距離」較小的點(diǎn)
????????????q?=?[(0,?x)]
????????????heapq.heapify(q)
????????????while?q:
????????????????#?每次從「優(yōu)先隊(duì)列」中彈出
????????????????step,?u?=?heapq.heappop(q)
????????????????#?如果彈出的點(diǎn)被標(biāo)記「已更新」，則跳過(guò)
????????????????if?vis[u]:?continue
????????????????#?標(biāo)記該點(diǎn)「已更新」，并使用該點(diǎn)更新其他點(diǎn)的「最短距離」
????????????????vis[u]?=?True
????????????????i?=?he[u]
????????????????while?i?!=?-1:
????????????????????j,?c?=?e[i],?w[i]
????????????????????i?=?ne[i]
????????????????????if?dist[j]?<=?dist[u]?+?c:?continue
????????????????????dist[j]?=?dist[u]?+?c
????????????????????heapq.heappush(q,?(dist[j],?j))
????????????return?dist

????????#「虛擬源點(diǎn)」向「第一行」進(jìn)行連邊
????????for?i?in?range(M):
????????????add(S,?grid[0][i],?grid[0][i])
????????#?轉(zhuǎn)換原圖
????????for?i?in?range(N?-?1):
????????????for?j?in?range(M):
????????????????a?=?grid[i][j]
????????????????for?k?in?range(M):
????????????????????b?=?grid[i?+?1][k]
????????????????????add(a,?b,?moveCost[a][k]?+?b)
????????#「最后一行」向「虛擬匯點(diǎn)」進(jìn)行連邊
????????for?i?in?range(M):
????????????add(grid[N?-?1][i],?T,?0)
????????#?最短路
????????dist?=?dijkstra(S)
????????return?dist[T]

• 時(shí)間復(fù)雜度： ，其中 為新圖中的點(diǎn)數(shù) ， 為新圖中的邊數(shù)
• 空間復(fù)雜度：

堆優(yōu)化 Dijkstra

什么？你說(shuō)你實(shí)在不想建新圖，也不想搞什么虛擬點(diǎn)，就想用你心愛(ài)的 BFS 來(lái)做？！

我懂你意思，但那不叫 BFS。

只是將「建新圖」和「建虛擬點(diǎn)」的過(guò)程省掉，仍需要使用優(yōu)先隊(duì)列（堆）來(lái)每次取出當(dāng)前“路徑代價(jià)最小”的點(diǎn)來(lái)進(jìn)行擴(kuò)充，執(zhí)行過(guò)程仍為堆優(yōu)化 Dijkstra 的核心操作。

尤其所謂“省掉” 建新圖 和 建虛擬點(diǎn)，真就字面上的“省掉”，并非不存在，因?yàn)閮煞N做法思路是完全一致的?？珊?jiǎn)單列舉「本解法」與「解法一」的對(duì)應(yīng)關(guān)系：

• 起始往隊(duì)列放入首行元素，對(duì)應(yīng)了解法一的“建立虛擬源點(diǎn)”過(guò)程；
• 從隊(duì)列中取元素出來(lái)擴(kuò)充時(shí)，若當(dāng)前元素所在行是最后一行時(shí)，用當(dāng)前路徑代價(jià)來(lái)更新答案，對(duì)應(yīng)了解法一的“建立虛擬匯點(diǎn)”過(guò)程；
• 擴(kuò)充時(shí)直接遍歷列（即下一行的所有點(diǎn)），對(duì)應(yīng)的解法一的“用原圖邊建新圖”的過(guò)程。

Java 代碼：

class?Solution?{
????public?int?minPathCost(int[][]?grid,?int[][]?moveCost)?{
????????int?m?=?grid.length,?n?=?grid[0].length,?INF?=?0x3f3f3f3f,?ans?=?INF;
????????int[][]?dist?=?new?int[m][n];
????????for?(int?i?=?0;?i?<?m;?i++)?{
????????????for?(int?j?=?0;?j?<?n;?j++)?dist[i][j]?=?INF;
????????}
????????PriorityQueue<int[]>?d?=?new?PriorityQueue<>((a,b)->a[2]-b[2]);
????????for?(int?i?=?0;?i?<?n;?i++)?{
????????????d.add(new?int[]{0,?i,?grid[0][i]});
????????????dist[0][i]?=?grid[0][i];
????????}
????????while?(!d.isEmpty())?{
????????????int[]?info?=?d.poll();
????????????int?x?=?info[0],?y?=?info[1],?cur?=?info[2];
????????????if?(x?==?m?-?1)?{
????????????????ans?=?Math.min(ans,?cur);
????????????????continue;
????????????}
????????????for?(int?i?=?0;?i?<?n;?i++)?{
????????????????int?step?=?moveCost[grid[x][y]][i],?ne?=?grid[x?+?1][i];
????????????????int?tot?=?cur?+?step?+?ne;
????????????????if?(tot?>=?ans?||?dist[x?+?1][i]?<=?tot)?continue;
????????????????dist[x?+?1][i]?=?tot;
????????????????d.add(new?int[]{x?+?1,?i,?tot});
????????????}
????????}
????????return?ans;
????}
}

C++ 代碼：

class?Solution?{
public:
????int?minPathCost(vector<vector<int>>&?grid,?vector<vector<int>>&?moveCost)?{
????????int?m?=?grid.size(),?n?=?grid[0].size(),?INF?=?0x3f3f3f3f,?ans?=?INF;
????????vector<vector<int>>?dist(m,?vector<int>(n,?INF));
????????priority_queue<vector<int>,?vector<vector<int>>,?greater<vector<int>>>?pq;
????????for?(int?i?=?0;?i?<?n;?i++)?{
????????????pq.push({0,?i,?grid[0][i]});
????????????dist[0][i]?=?grid[0][i];
????????}
????????while?(!pq.empty())?{
????????????vector<int>?info?=?pq.top();
????????????pq.pop();
????????????int?x?=?info[0],?y?=?info[1],?cur?=?info[2];
????????????if?(x?==?m?-?1)?{
????????????????ans?=?min(ans,?cur);
????????????????continue;
????????????}
????????????for?(int?i?=?0;?i?<?n;?i++)?{
????????????????int?step?=?moveCost[grid[x][y]][i],?ne?=?grid[x?+?1][i];
????????????????int?tot?=?cur?+?step?+?ne;
????????????????if?(tot?>=?ans?||?dist[x?+?1][i]?<=?tot)?continue;
????????????????dist[x?+?1][i]?=?tot;
????????????????pq.push({x?+?1,?i,?tot});
????????????}
????????}
????????return?ans;
????}
};

Python 代碼：

class?Solution:
????def?minPathCost(self,?grid,?moveCost):
????????m,?n,?INF?=?len(grid),?len(grid[0]),?float('inf')
????????ans?=?INF
????????dist?=?[[INF]?*?n?for?_?in?range(m)]
????????for?i?in?range(n):
????????????dist[0][i]?=?grid[0][i]
????????pq?=?[(0,?i,?grid[0][i])?for?i?in?range(n)]
????????while?pq:
????????????x,?y,?cur?=?heapq.heappop(pq)
????????????if?x?==?m?-?1:
????????????????ans?=?min(ans,?cur)
????????????????continue
????????????for?i?in?range(n):
????????????????step,?ne?=?moveCost[grid[x][y]][i],?grid[x?+?1][i]
????????????????tot?=?cur?+?step?+?ne
????????????????if?tot?>=?ans?or?dist[x?+?1][i]?<=?tot:?continue
????????????????dist[x?+?1][i]?=?tot
????????????????heapq.heappush(pq,?(x?+?1,?i,?tot))
????????return?ans

• 時(shí)間復(fù)雜度： ，其中 為新圖中的點(diǎn)數(shù) ， 為新圖中的邊數(shù)
• 空間復(fù)雜度：

原地模擬

什么？你說(shuō)你連圖論的方法都不想用，想就著題意做一遍？

可以。甚至當(dāng)你調(diào)整更新方向，還能利用已有的 grid，實(shí)現(xiàn)原地模擬。

具體的，我們將“從上往下走”調(diào)整為“從下往上走”，這樣可以確保當(dāng)我們使用底下一行 來(lái)更新當(dāng)前行 時(shí)，所用到的 不會(huì)被覆蓋。

Java 代碼：

class?Solution?{
????public?int?minPathCost(int[][]?grid,?int[][]?moveCost)?{
????????int?m?=?grid.length,?n?=?grid[0].length,?INF?=?0x3f3f3f3f,?ans?=?INF;
????????for?(int?i?=?m?-?2;?i?>=?0;?i--)?{
????????????for?(int?j?=?0;?j?<?n;?j++)?{
????????????????int?cur?=?INF;
????????????????for?(int?k?=?0;?k?<?n;?k++)?cur?=?Math.min(cur,?grid[i?+?1][k]?+?moveCost[grid[i][j]][k]);
????????????????grid[i][j]?+=?cur;
????????????}
????????}
????????for?(int?i?=?0;?i?<?n;?i++)?ans?=?Math.min(ans,?grid[0][i]);
????????return?ans;
????}
}

C++ 代碼：

class?Solution?{
public:
????int?minPathCost(vector<vector<int>>&?grid,?vector<vector<int>>&?moveCost)?{
????????int?m?=?grid.size(),?n?=?grid[0].size(),?INF?=?INT_MAX,?ans?=?INF;
????????for?(int?i?=?m?-?2;?i?>=?0;?i--)?{
????????????for?(int?j?=?0;?j?<?n;?j++)?{
????????????????int?cur?=?INF;
????????????????for?(int?k?=?0;?k?<?n;?k++)?cur?=?min(cur,?grid[i?+?1][k]?+?moveCost[grid[i][j]][k]);
????????????????grid[i][j]?+=?cur;
????????????}
????????}
????????for?(int?i?=?0;?i?<?n;?i++)?ans?=?min(ans,?grid[0][i]);
????????return?ans;
????}
};

Python 代碼：

class?Solution:
????def?minPathCost(self,?grid,?moveCost):
????????m,?n?=?len(grid),?len(grid[0])
????????for?i?in?range(m?-?2,?-1,?-1):
????????????for?j?in?range(n):
????????????????grid[i][j]?+=?min([grid[i?+?1][k]?+?moveCost[grid[i][j]][k]?for?k?in?range(n)])
????????return?min([grid[0][i]?for?i?in?range(n)])

TypeScript 代碼：

function?minPathCost(grid:?number[][],?moveCost:?number[][]):?number?{
????let?m?=?grid.length,?n?=?grid[0].length,?INF?=?0x3f3f3f3f,?ans?=?INF;
????for?(let?i?=?m?-?2;?i?>=?0;?i--)?{
????????for?(let?j?=?0;?j?<?n;?j++)?{
????????????let?cur?=?INF;
????????????for?(let?k?=?0;?k?<?n;?k++)?cur?=?Math.min(cur,?grid[i?+?1][k]?+?moveCost[grid[i][j]][k]);
????????????grid[i][j]?+=?cur;
????????}
????}
????for?(let?i?=?0;?i?<?n;?i++)?ans?=?Math.min(ans,?grid[0][i]);
????return?ans;
};

• 時(shí)間復(fù)雜度： ，其中 和 分別代表給定 grid 的長(zhǎng)寬
• 空間復(fù)雜度：

最后

這是我們「刷穿 LeetCode」系列文章的第 No.2304 篇，系列開(kāi)始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們將先把所有不帶鎖的題目刷完。

在這個(gè)系列文章里面，除了講解解題思路以外，還會(huì)盡可能給出最為簡(jiǎn)潔的代碼。如果涉及通解還會(huì)相應(yīng)的代碼模板。

為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼，我建立了相關(guān)的倉(cāng)庫(kù)：https://github.com/SharingSource/LogicStack-LeetCode 。

在倉(cāng)庫(kù)地址里，你可以看到系列文章的題解鏈接、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和其他優(yōu)選題解。

更多更全更熱門(mén)的「筆試/面試」相關(guān)資料可訪問(wèn)排版精美的 合集新基地 ????文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-818136.html