Dijkstra算法——不帶負權的單源最短路徑

算法學習

算法原理

稠密圖Dijkstra模板

稀疏圖Dijkstra模板

練習

1 網絡延遲時間

2 到達最后一個房間的最少時間Ⅰ

3 到達最后一個房間的最少時間Ⅱ

4 訪問消失節點的最少時間

5 設計可以求最短路徑的圖類

6 概率最大的路徑

7 最小體力消耗路徑?

8 從第一個節點出發到最后一個節點的受限路徑數

9 最短路徑中的邊

10 到達目的地的方案數

11 水位上升的泳池中游泳

12 前往目標的最小代價

13 使兩個整數相等的數位操作

算法學習

算法原理

迪杰斯特拉(Dijkstra)算法是用于解決只有非負權值的圖的單源最短路徑問題的算法。

迪杰斯特拉本質是一種局部貪心的思路，算法過程如下：

1 將圖中所有的節點分為兩個集合，S和Q，S為以確定最短路徑的節點的集合，而Q為未確定最短路徑的節點的集合。

在初始條件下，只有起點是確定最短路徑的，為0，所以初始條件 S中只有起點，其他的節點都在Q中，后續每確定起點到一個節點的最短路徑，就會將對應節點從Q中移除，加入到S中。

2 每一次從 Q 中找一個起點到該節點代價最小(路徑最短，權值最小)的節點u。

每一輪我們都能確定一個點，起點到該點的最短路徑能夠確定。

3 將u從Q中移除，加入到S，然后對u的每一個相鄰節點進行松弛操作。

松弛操作我們可以簡單理解為：嘗試從已確定最短路的節點前往所有的鄰節點，看是否能夠得到更小的路徑。對于未確定最短路徑的所有節點，從起點有一條或者多條路徑能夠到達該店，所以從起點到達該點的路徑有多種值。我們每有一個確定最短路徑的節點，會嘗試從這個點去到達所有未確定最短路徑的鄰節點，如果從本點到鄰節點的路徑比當前記錄的路徑要小，我們可以更新鄰節點的路徑為從起點到本節點，再從本節點到鄰節點。

這樣文字講述起來其實并不好理解，我們可以用示例來分析，假設我們有這樣一個圖：

圖為有向圖，起點為0節點，我們需要求出從起點到達其他四個節點的最短路徑。

我們需要一個dis數組來保存起點到所有結點的最短路徑，在Dijkstra過程中可能保存的是當前所記錄的最短路徑。 dis[i] 表示從起點到節點 i 的最短路徑。

首先集合 S 中只有一個節點 S{0}，其中dis[0] = 0；然后我們需要從0節點對他的所有鄰節點進行松弛操作，于是 dis數組就更新為了: dis = [0，5，7，13，11 ]；

下一步從Q中選取一個路徑最短的節點，本輪選取的節點為節點1，因為dis[1] < dis[2] < dis[4] < dis[3]。那么我們本輪就能確定從起點到節點1的最短路徑就是當前dis數組中記錄的最短路徑。

為什么呢？因為圖中所有的邊的權值都非負，而從起點到節點1如果有很多的走法，不管從哪一條路徑走，都會首先經過至少一個中間點，假設中間點為 x ，因為 dis{0->1}的路徑已經是所有的dis中最小的了，那么到達中間點x的路徑為 dis[x] ，本身 dis[1] <= dis[x]，而從中間點x到節點1還至少需要走一條邊，假設邊的權值為 y ，而y >= 0 ，那么從中間節點x到節點1的路徑就為 dis[x] + y，而 dis[1] <= dis[x] + y，說明直接從起點走到節點1的路徑，一定是小于等于從其他的中間節點走到節點1的，那么最壞情況下，dis[1] == dis[x] + y ，此時我們的 dis[1] 仍然是最短路徑。?這其實是一種局部貪心的策略。?

那么我們將節點1從Q加入到S之后，還需要對節點1的鄰節點進行松弛操作。

那么在本輪結束之后，我們就能夠確定0和1的最短路徑，下一步就繼續從Q中選取一個最短路徑的節點，本輪取出的節點為節點 2 ，因為 dis[2] < dis[4] < dis[3]；所以當前的 dis[2] 就是從起點到節點2的最短路徑，理由如上。因為當前已經確定最短路徑的節點只有0和1，那么我們需要判斷從節點0或者節點1到達Q中的點的所有路徑中，最小的路徑，而我們初始情況下dis數組中記錄的就是從節點0到達所有節點的路徑，而在第一輪取出節點1的時候，又更新了dis數組，dis數組中當前保存的是 從節點0直接到該點的路徑以及從節點0先沿最短路徑到達節點1，再從節點1到達目標點，這兩種路徑中的較小路徑。那么Q中未確定最短路徑的節點中，最小的路徑為節點2的路徑，這已經是 dis[2] = min {dis{0->2} , dis{0->1->2}}，也就是min{dis{0->x->2}} x為S中的節點，到達節點2還可能有其他的路徑，也就是先從0到達Q的節點，再去往節點2，但是由于當前所記錄的 dis 中，從起點到達Q中所有的節點的路徑都大于等于 dis[2] ，那么從起點到達這些節點本身路徑就大于等于dis[2]了，再加上從該點到達節點2，路徑只會更大，所以dis[2]已經是最優解了。

然后我們再對2的鄰節點進行松弛操作。

那么以此類推，下一個從Q中取出或者說能夠確定最短路徑的節點就是節點 4 ，節點4取出來之后，松弛操作之后的 dis = [0,5,7,11,9]

最后再取出節點 3，松弛操作之后，dis = [0,5,7,11,9]。

那么這樣一來，所有的節點都已經確定了最短路徑，而最短路徑就保存在dis數組中。

在Dijkstra的過程中，可能在某一輪的時候，有些節點還沒有任何路徑能夠到達，比如下面的這個圖：

在初始情況下，并沒有從節點0到達節點4的邊，那么起始的 dis[4]其實是未定義的，或者沒有路徑到達，那么如何定義呢？由于后續我們需要從dis數組中取出一個未確定最短路徑的最小值，也就是取min，那么為了讓這些點不影響這個過程，我們需要將其初始化為正無窮大 0x3f3f3f3f。

還有就是如果最終圖中的某些節點根本無法到達，也就是某一輪選出的最小的 dis = 0x3f3f3f3f，說明這些節點無法從起點到達，那么我們可以提前結束Dijkstra的過程。

以上是使用單向圖來舉例，雙向圖的Dijkstra也是一樣的思路。

#include<iostream>
#include<vector>
using namespace std;vector<int> Dijkstra(int n, const vector<vector<int>>& grid, int k) {}int main() {int n = 5; //節點個數vector<vector<int>> grid{ {0,1,5},{0,2,7},{0,3,13},{0,4,11},{1,3,6},{1,4,4},{2,3,7},{2,4,3} }; //邊,每一個grid[i]也就是 [x,y,z] 表示的是從x到y有一條邊，權值為zint k = 0; //起點vector<int> dis = Dijkstra(n, grid, k);return 0;
}

根據圖和邊的比例，或者說稠密圖和稀疏圖，有兩種做法，當然思路是一樣的，只是代碼形式有所不同。

稠密圖Dijkstra模板

對于稠密圖，也就是幾乎所有的兩個節點之間都有邊，那么此時使用鄰接矩陣來存儲邊的關系更加適合。

鄰接矩陣 g[i][j] ，表示的是從節點 i 到節點 j 之間有一條邊，權值為 g[i][j] ，當然也可能不存在，我們可以定義 i 到 j 沒有直接邊相連時，g[i][j] = -1;

如果是雙向圖，對于[i,j,z]表示的是i到j和j到i都有一條邊，權值都為z，那么從事 g[i][j] = g[j][i] =z;

那么第一步就是創建一個鄰接矩陣：

	vector<vector<int>> g(n, vector<int>(n, -1));for (auto& v : grid) g[v[0]][v[1]] = v[2];

第二步就是創建一個dis數組，用于記錄最短路徑，還需要一個數組 S ,s[i]用于記錄節點是否已確定最短路徑,并對起點進行初始化;

	const int INF = 0x3f3f3f3f;vector<int> dis(n, INF);  //記錄路徑vector<bool> S(n, false); //記錄節點是否已確定最短路徑//初始化dis[k] = 0;

注意在這里我們并沒有對 S[k] 進行初始化，這樣一來可以在循環的過程中對起點k的所有鄰節點進行松弛操作，節省了我們對 k 的鄰節點初始化的工作量。

//稠密圖Dijkstra
vector<int> Dijkstra(int n, const vector<vector<int>>& grid, int k) {  //初始化鄰接矩陣vector<vector<int>> g(n, vector<int>(n, -1));for (auto& v : grid) g[v[0]][v[1]] = v[2];const int INF = 0x3f3f3f3f;vector<int> dis(n, INF);  //記錄路徑vector<bool> S(n, false); //記錄節點是否已確定最短路徑//初始化dis[k] = 0;//取最短路徑并進行松弛操作while (1) {//首先需要找到一個未確定最短路徑的節點中的最短路徑int x = -1 , mindis = INF;	for(int i = 0 ; i < n ; ++i){if (!S[i] && dis[i] < mindis) {  //注意這里是 dis[i] < mindisx = i, mindis = dis[i];}}if (x == -1) break; //此時有兩種情況：1、所有節點的最短路徑都已確定； 2、有節點不可達，此時也不需要繼續進行松弛//然后對 i 的鄰節點進行松弛操作S[x] = true;for (int j = 0; j < n; ++j) {if (!S[j] && g[x][j] != -1 && mindis + g[x][j] < dis[j]) { //三個條件：Q中的節點，x->j有邊， dis[k->x->j] < dis[j]dis[j] = mindis + g[x][j];}}}return dis;
}

稀疏圖Dijkstra模板

對于稠密圖，由于邊的數量很多很多，那么在遍歷 g[i][j]的時候，大多數都是有效遍歷，也就是g[i][j] > -1，但是對于稀疏圖，也就是邊的數量遠小于點的數量的平方，那么此時如果使用鄰接矩陣的話，就會導致大部分的位置上都是-1，空間浪費過大，同時在遍歷g[i][j]的時候，大多數都是無效遍歷，所以稀疏圖不適合采用鄰接矩陣來存儲邊，而采用鄰接表。
鄰接表其實也很簡單，我們也可以用二維數組來存儲，只不過不是直接開 n* n的空間，而是根據具體的邊的數量來開辟空間。

鄰接表可以使用 vector<vector<pair<int,int>>> 來存儲?

對于g[i] ，是一個一維數組，每一個元素是pair<int,int>，其中 first 存儲的是節點的編號，int存儲的是邊的權值， g[i][j] 表示的是從節點 i 到節點 g[i][j].first 存在一條邊，邊的權值為 g[i][j].second。

那么我們可以這樣初始化鄰接表：

	vector<vector<pair<int, int>>> g;//鄰接矩陣for (auto& v : grid) g[v[0]].emplace_back(v[1], v[2]);

同時，對于算法的過程，我們也可以優化。

由于我們會多次求dis中最小的路徑，那么我們其實可以將未確定的節點在dis中記錄的路徑放到一個最小堆中，后續我們直接去堆頂的元素，就能拿到最短路徑。

我們使用這樣一個堆來存儲：

	class mygreater {public:bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) { return p1.second > p2.second; }};priority_queue<pair<int, int>, vector<pair<int, int>>, mygreater> pq;		//first存節點的編號，second存路徑

但是這樣有一個問題：

按照上面的流程，我們在第一輪循環中，會將1~4節點都入堆，此時堆中有節點1，2，3，4的路徑

在第二輪循環中，我們會取出節點1，并對節點1的鄰節點進行松弛操作，那么此時如果發現對應的dis需要更新，那么就需要對該節點以及更新后的路徑再次入堆，也就是會對3和4再次入堆。

那么此時堆中就有兩個節點3和4的路徑信息，那么兩次出堆都需要更新最短路徑以及松弛操作嗎？

很簡單，對于堆中同一個節點的多個路徑，我們只會用到最小的，同時，該節點的最短路徑一定是第一個出堆的該節點的pair，當第一個該節點的鍵值對出堆的時候，最短路徑就確定了，此時dis數組中記錄的就是這個最短路徑，那么需要進行松弛操作，后續再次出堆，此時的 second 保存的路徑一定大于 dis 中的路徑，那么此時就不再需要進行松弛操作。

在使用堆來優化的情況下，既提高了找最小值的效率，也節省了S數組的空間。

代碼如下：

//稀疏圖Dijkstra
vector<int> Dijkstra(int n, const vector<vector<int>>& grid, int k) {vector<vector<pair<int, int>>> g(n);//鄰接矩陣for (auto& v : grid) g[v[0]].emplace_back(v[1], v[2]);  //first存儲邊的目的節點，second存儲邊的權值const int INF = 0x3f3f3f3f;vector<int>dis(n, INF);class mygreater {public:bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) { return p1.second > p2.second; }};priority_queue<pair<int, int>, vector<pair<int, int>>, mygreater> pq;		//first存節點的編號，second存路徑//首先將起點入堆dis[k] = 0;pq.emplace(0, 0);while (!pq.empty()) {auto p = pq.top();pq.pop();if (dis[p.first] > p.second) continue; //非第一次出堆//走到這里說明 dis[p.firrst] == p.second//那么說明是對應節點的路徑信息第一次出堆，本次出堆的一定是最小路徑，那么需要進行松弛操作int mindis = p.second, x = p.first;//松弛操作for (auto& pj : g[x]) //對x的出邊遍歷{if (mindis + pj.second < dis[pj.first])  //說明從k 到  x 再到 j 的路徑小于當前dis數組記錄的 k到j的路徑，那么需要更新{dis[pj.first] = mindis + pj.second;//入堆pq.emplace(pj.first, dis[pj.first]);}}}//走到這里堆為空，如果有不可到達的節點，那么dis數組不會發生任何更新，保存的還是 INFreturn dis;
}

練習

1 網絡延遲時間

743. 網絡延遲時間 - 力扣（LeetCode）

題目解析：題目給我們所有的邊，節點總數，以及起點，要我們求起點傳播到其他點的最遠時間，如果有節點無法到達，返回-1，如果所有點都可到達，那么需要返回最遠的點的最短路徑。

本題就是一個標準的Dijkstra問題，需要求出起點到所有點最短路徑，在算法題中，我們一般就認為是稀疏圖，一般都是使用鄰接表來存儲邊，而Dijkstra的過程其實就和我們的模板一樣。

但是要注意的一點就是一般題目中給的節點編號是從1開始，而不是0開始。

代碼如下：

class Solution {
public:const int INF = 0x3f3f3f3f;class mygreater{public:bool operator()(const pair<int,int>&p1,const pair<int,int>&p2){return p1.second > p2.second;}    };int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<pair<int,int>>> g(n+1);  //g[i] 存儲節點i的邊for(auto&v:times) g[v[0]].emplace_back(v[1],v[2]);vector<int> dis (n+1 , INF);priority_queue<pair<int,int>,vector<pair<int,int>>,mygreater> pq;dis[k] = 0;pq.emplace(k,0);while(!pq.empty()){auto p = pq.top();pq.pop();if(p.second > dis[p.first]) continue; //不是第一次出堆int x = p.first , mindis = p.second;//松弛操作for(auto& py : g[x]){if(mindis + py.second < dis[py.first]){ //更新dis[py.first] = mindis + py.second;pq.emplace(py.first,dis[py.first]);}}}int res = -INF;for(int i = 1 ; i <= n ; ++i){res = max(res , dis[i]);}return res == INF ? -1 : res; }
};

2 到達最后一個房間的最少時間Ⅰ

3341. 到達最后一個房間的最少時間 I - 力扣（LeetCode）

題目解析：一共有 n*m 個房間，每個房間有一個最小開啟時間，也就是在這個時間之前，無法向該房間移動，比如times[1][1]=3，那么在第3s之前無法向{1,1}移動。? 每一次移動只能移動到相鄰的房間，也就是上下左右四個房間，相鄰房間的移動需要耗時一秒，返回到達{m-1.n-1}房間的最少時間。

題目隱含的信息其實有兩個：

1、每一個節點有四條邊，與其上下左右四個節點直接相連。

2、每一條邊的權值為1。

但是本題在求最短路徑的時候有一個限制，假設我們更新了 {i,j} 的最短時間dis[i][j]，那么更新dis[i+1][j]的時候，除了要考慮dis[i][j] 的大小之外，還需要考慮能夠前往{i+1,j}的最短時間，也就是moveTime[i+1][j] ，最早在這個時間才能開始向{i+1,j}開始移動，而移動需要耗時1s，那么到達{i+1,j}房間的最早時間就是 moveTime[i+1][j]+1，所以如果我們使用 dis[i][j] + 1 算出來的時間比 moveTime[i+1][j]+1小，那么此時最早到達時間是 moveTime[i+1][j] + 1;

還有就是由于這里的節點是一個二元組，那么我們就需要保存二元組的位置以及路徑，那么我們可以直接使用一個vector來入堆，后續出堆的時候就能很快提取位置和路徑。

其他的地方沒有需要修改的。

class Solution {
public:const int INF = 0x3f3f3f3f;class mygreater{public:bool operator()(const vector<int>&v1,const vector<int>&v2){return v1[2] > v2[2];}};int minTimeToReach(vector<vector<int>>& moveTime) {int m = moveTime.size() , n = moveTime[0].size();vector<vector<int>> dis(m,vector<int>(n,INF));//起點為 0,0dis[0][0] = 0;priority_queue<vector<int>,vector<vector<int>>,mygreater> pq;pq.push({0,0,0}); while(!pq.empty()){//取出堆頂元素auto v = pq.top();pq.pop();//判斷是不是最短路徑第一次出棧if(v[2] >dis[v[0]][v[1]]) continue;int x = v[0] , y = v[1] , mindis = v[2];if(x > 0 && (dis[x-1][y] == INF || max(mindis , moveTime[x-1][y]) + 1 < dis[x-1][y])){ //更新(x-1,y)dis[x-1][y] = max(mindis , moveTime[x-1][y]) + 1;pq.push({x-1,y,dis[x-1][y]});}if(y > 0 && (dis[x][y-1] == INF || max(mindis , moveTime[x][y-1]) + 1 < dis[x][y-1])){ //更新(x,y-1)dis[x][y-1] = max(mindis , moveTime[x][y-1]) + 1;pq.push({x,y-1,dis[x][y-1]});}if(x + 1 < m && (dis[x+1][y] == INF || max(mindis,moveTime[x+1][y]) + 1 < dis[x+1][y])){//更新(x+1,y)dis[x+1][y] = max(mindis,moveTime[x+1][y]) + 1;pq.push({x+1,y,dis[x+1][y]});}if(y + 1 < n && (dis[x][y+1] == INF || max(mindis,moveTime[x][y+1]) + 1 < dis[x][y+1])){//更新(x,y+1)dis[x][y+1] = max(mindis,moveTime[x][y+1]) + 1;pq.push({x,y+1,dis[x][y+1]});}}    return dis[m-1][n-1];}
};

同時，在這種只需要求一個點的最短路徑的情況下，其實是完全有可能提前求出來的，也就是說，我們并不需要求出所有的點的dis，而是只需要目標點，那么在出堆的過程中，如果目標點第一次出堆，一定是最短路徑，此時我們就可以直接返回了，這也算是一個小優化。

class Solution {
public:const int INF = 0x3f3f3f3f;class mygreater{public:bool operator()(const vector<int>&v1,const vector<int>&v2){return v1[2] > v2[2];}};int minTimeToReach(vector<vector<int>>& moveTime) {int m = moveTime.size() , n = moveTime[0].size();vector<vector<int>> dis(m,vector<int>(n,INF));//起點為 0,0dis[0][0] = 0;priority_queue<vector<int>,vector<vector<int>>,mygreater> pq;pq.push({0,0,0}); while(!pq.empty()){//取出堆頂元素auto v = pq.top();pq.pop();//判斷是不是最短路徑第一次出棧if(v[2] >dis[v[0]][v[1]]) continue;int x = v[0] , y = v[1] , mindis = v[2];if(x == m-1 && y == n-1) return mindis;         //提前結束if(x > 0 && (dis[x-1][y] == INF || max(mindis , moveTime[x-1][y]) + 1 < dis[x-1][y])){ //更新(x-1,y)dis[x-1][y] = max(mindis , moveTime[x-1][y]) + 1;pq.push({x-1,y,dis[x-1][y]});}if(y > 0 && (dis[x][y-1] == INF || max(mindis , moveTime[x][y-1]) + 1 < dis[x][y-1])){ //更新(x,y-1)dis[x][y-1] = max(mindis , moveTime[x][y-1]) + 1;pq.push({x,y-1,dis[x][y-1]});}if(x + 1 < m && (dis[x+1][y] == INF || max(mindis,moveTime[x+1][y]) + 1 < dis[x+1][y])){//更新(x+1,y)dis[x+1][y] = max(mindis,moveTime[x+1][y]) + 1;pq.push({x+1,y,dis[x+1][y]});}if(y + 1 < n && (dis[x][y+1] == INF || max(mindis,moveTime[x][y+1]) + 1 < dis[x][y+1])){//更新(x,y+1)dis[x][y+1] = max(mindis,moveTime[x][y+1]) + 1;pq.push({x,y+1,dis[x][y+1]});}}    return dis[m-1][n-1];}
};

3 到達最后一個房間的最少時間Ⅱ

3342. 到達最后一個房間的最少時間 II - 力扣（LeetCode）

解析題目：本題與上一題是一個類型的題目，也有可以前往對應房間的最早時間的限制，但是本題還多出了一個限制，就是如果是第奇數次移動，那么本次移動需要1秒，如果是第偶數次移動，那么本次移動需要2秒。

其實暴力的方法很簡單，我們再入堆的時候，直接再添加一個元素，就是下一次移動是第幾次，那么后續我們進行松弛操作的時候就能知道下一次移動需要1秒還是2秒。代碼如下：

class Solution {
public:const int INF = 0x3f3f3f3f;class mygreater{public:bool operator()(const vector<int>&v1,const vector<int>&v2){return v1[3] > v2[3] ; }};int minTimeToReach(vector<vector<int>>& moveTime) {int m = moveTime.size(), n = moveTime[0].size();vector<vector<int>> dis(m,vector<int>(n,INF));priority_queue<vector<int>,vector<vector<int>>,mygreater> pq;dis[0][0] = 0;pq.push({0,0,1,0});  //v[0]表示橫坐標，v[1]表示縱坐標，v[2]表示下一次移動是第幾次移動，v[3]表示路徑長度while(!pq.empty()){auto v = pq.top();pq.pop();int x = v[0] , y = v[1] , cnt = v[2] , mindis = v[3] , t = 2 - cnt % 2;  //t表示松弛操作的時間，也就是下一次移動所需要的時間if(mindis > dis[x][y]) continue;if(x == m - 1 && y == n - 1) return mindis;if(x > 0 && (dis[x-1][y] == INF || max(mindis , moveTime[x-1][y]) + t < dis[x-1][y])){ //更新(x-1,y)dis[x-1][y] = max(mindis , moveTime[x-1][y]) + t;pq.push({x-1,y,cnt+1,dis[x-1][y]});}if(y > 0 && (dis[x][y-1] == INF || max(mindis , moveTime[x][y-1]) + t < dis[x][y-1])){ //更新(x,y-1)dis[x][y-1] = max(mindis , moveTime[x][y-1]) + t;pq.push({x,y-1,cnt+1,dis[x][y-1]});}if(x + 1 < m && (dis[x+1][y] == INF || max(mindis , moveTime[x+1][y]) + t < dis[x+1][y])){ //更新(x+1,y)dis[x+1][y] = max(mindis , moveTime[x+1][y]) + t;pq.push({x+1,y,cnt+1,dis[x+1][y]});}if(y + 1 < n && (dis[x][y+1] == INF || max(mindis , moveTime[x][y+1]) + t < dis[x][y+1])){ //更新(x,y+1)dis[x][y+1] = max(mindis , moveTime[x][y+1]) + t;pq.push({x,y+1,cnt+1,dis[x][y+1]});}}return dis[m-1][n-1];}
};

本題還有一種更巧妙的做法，其實對于這種網格圖，我們從當前位置的坐標，就能知道下一次移動是奇數次還是偶數次移動。

我們的起點是 (0,0) ，兩個坐標都是偶數，那么橫縱坐標之和也是偶數，下一次移動就是第一次移動。移動的時候，是將橫坐標加以或者減一?或者縱坐標加一或者減一，那么不管怎么說，都會導致其中一個坐標變成奇數，那么橫縱坐標值和就變成了奇數。

而對于(0,1)，兩個坐標之和為奇數，下一次移動一定是第偶數次移動，因為只有經歷奇數次移動才會使橫縱坐標之和為奇數。

那么我們就能夠根據當前所處的房間的下標(x,y)推導出下一次移動是第奇數次移動還是第偶數次移動，如果x+y是奇數，那么下一次就是第偶數次移動，如果x+y是偶數，那么下一次就是第奇數次移動。

代碼如下：

class Solution {
public:const int INF = 0x3f3f3f3f;class mygreater{public:bool operator()(const vector<int>&v1,const vector<int>&v2){return v1[2] > v2[2] ; }};int minTimeToReach(vector<vector<int>>& moveTime) {int m = moveTime.size(), n = moveTime[0].size();vector<vector<int>> dis(m,vector<int>(n,INF));priority_queue<vector<int>,vector<vector<int>>,mygreater> pq;dis[0][0] = 0;pq.push({0,0,0});  //v[0]表示橫坐標，v[1]表示縱坐標，v[2]表示下一次移動是第幾次移動，v[3]表示路徑長度while(!pq.empty()){auto v = pq.top();pq.pop();int x = v[0] , y = v[1] , mindis = v[2] , t = 1 + (x + y) % 2;  //t表示松弛操作的時間，也就是下一次移動所需要的時間if(mindis > dis[x][y]) continue;if(x == m - 1 && y == n - 1) return mindis;if(x > 0 && (dis[x-1][y] == INF || max(mindis , moveTime[x-1][y]) + t < dis[x-1][y])){ //更新(x-1,y)dis[x-1][y] = max(mindis , moveTime[x-1][y]) + t;pq.push({x-1,y,dis[x-1][y]});}if(y > 0 && (dis[x][y-1] == INF || max(mindis , moveTime[x][y-1]) + t < dis[x][y-1])){ //更新(x,y-1)dis[x][y-1] = max(mindis , moveTime[x][y-1]) + t;pq.push({x,y-1,dis[x][y-1]});}if(x + 1 < m && (dis[x+1][y] == INF || max(mindis , moveTime[x+1][y]) + t < dis[x+1][y])){ //更新(x+1,y)dis[x+1][y] = max(mindis , moveTime[x+1][y]) + t;pq.push({x+1,y,dis[x+1][y]});}if(y + 1 < n && (dis[x][y+1] == INF || max(mindis , moveTime[x][y+1]) + t < dis[x][y+1])){ //更新(x,y+1)dis[x][y+1] = max(mindis , moveTime[x][y+1]) + t;pq.push({x,y+1,dis[x][y+1]});}}return dis[m-1][n-1];}
};

4 訪問消失節點的最少時間

3112. 訪問消失節點的最少時間 - 力扣（LeetCode）

解析題目：給定圖的邊，同時給定每個節點的消失時間，當到達時間大于等于節點的消失時間的時候，那么該節點無法到達。

本題相較于直接求最短路徑多出了一個限制條件，也就是每個節點有一個消失的時間，我們只有在消失時間之前到達該節點才是有效的。

那么就有兩種情況：

1、到達節點i的最短路徑 dis[i] < disqppear[i] ，那么此時節點 i 是可到達的，需要進行松弛操作。

2、到達節點的最短路徑 dis[i] >= disappear[i]，那么此時節點i是不可達的，那么自然也無法通過該節點去往其他節點，那么不需要進行松弛操作，同時需要將dis[i] 置為-1，表示不可達。

其他的思路則還是和單源最短路徑一樣。

代碼如下：

class Solution {class mygreater{public:bool operator()(const vector<int>&v1,const vector<int>&v2){return v1[1] > v2[1];}};const int INF = 0x3f3f3f3f;
public:vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {vector<int> dis(n,INF);vector<vector<pair<int,int>>> g(n);  //鄰接表for(auto& v: edges){g[v[0]].push_back(make_pair(v[1],v[2])); g[v[1]].push_back(make_pair(v[0],v[2]));  //注意題目的圖是雙向圖}priority_queue<vector<int>,vector<vector<int>>,mygreater> pq;pq.push({0,0});dis[0] = 0;while(!pq.empty()){auto v = pq.top();pq.pop();if(v[1] > dis[v[0]]) continue;  //如果v[0]最短路已經不可達了，那么此時dis[v[0]] == -1,走當前if出去了 else if(v[1] >= disappear[v[0]]){  //走到這里說明本輪出堆的已經是最短路，最早到達時間dis[v[0]] = -1; //說明最早到達時間節點已經消失，那么無法到達continue;}else{   //v[0]節點消失之前可到達，那么需要松弛操作for(auto&p : g[v[0]]){  //g[v[0]]的鄰邊if(dis[p.first] == INF||p.second + v[1] < dis[p.first]){dis[p.first] = v[1] + p.second;  //在這里先不判斷 v1[1] + p.second < disappear[i]，出堆再判斷pq.push({p.first,dis[p.first]});}}}}//再將不可達的點標記出來for(auto& e:dis) if(e == INF) e=-1;return dis;}
};

5 設計可以求最短路徑的圖類

2642. 設計可以求最短路徑的圖類 - 力扣（LeetCode）

解析題目：題目要求我們設計一個類，構造函數初始化節點的個數，初始邊的情況。然后還需要實現兩個函數，一個用于添加有向邊，一個用于求兩個節點的最短路徑。那么其實很簡單，我們可以使用鄰接表來保存邊的集合，而求最短路徑的時候，由于題目給出了邊的權值是大于1的，所以我么可以直接使用Dijkstra算法來求。雖然題目還提示了調用函數的次數，但是Dijkstra算法的時間復雜度并不高，相當于?O(M+N)，M為點的數量，N為邊的數量，所以還是能夠解決的。

那么代碼如下：

class Graph {
public:
class mygreater{
public:bool operator()(const vector<int>&v1,const vector<int>&v2){return v1[1] > v2[1];}
};Graph(int n, vector<vector<int>>& edges) :_n(n),_g(n){for(auto& v : edges)_g[v[0]].push_back(make_pair(v[1],v[2]));    } void addEdge(vector<int> edge) {_g[edge[0]].push_back(make_pair(edge[1],edge[2]));}int shortestPath(int node1, int node2) {vector<int> dis(_n,INF);dis[node1] = 0;_pq.push({node1,0});while(!_pq.empty()){auto v = _pq.top();_pq.pop();if(dis[v[0]] < v[1]) continue;for(auto& p : _g[v[0]]){if(p.second + v[1] < dis[p.first]){dis[p.first] = v[1] + p.second;_pq.push({p.first,dis[p.first]});}}}while(!_pq.empty()) _pq.pop();return dis[node2] == INF ? -1 : dis[node2];}
private:const int INF = 0x3f3f3f3f;int _n;vector<vector<pair<int,int>>> _g;priority_queue<vector<int>,vector<vector<int>>,mygreater>_pq;
};

6 概率最大的路徑

1514. 概率最大的路徑 - 力扣（LeetCode）

解析題目：題目給定一些邊，同時每一條邊都只有 succProb[i] 的概率能夠通過，要求我們求出從起點到重點的所有路徑中，通過概率最大的路徑的概率。對于一條路徑的通過概率，等于他的所有的邊的概率的乘積。

那么初看這個題好像是求最大的概率，那么好像并不是求最小路經，但是我們可以借鑒Dijkstra的思想。

題目給定所有的概率succProb[i] <= 1 ，那么其實如果從起點開始，走向起點的鄰邊，那么會有一條通過概率最大的邊，那么從起點通過改變到達該點，就是從起點到該點的最大概率路徑，因為所有的邊的概率都小于等于1，如果從其他的路徑走，最終到達該點的也不會超過這個概率，那么我們其實可以使用一個最大堆來模擬這個過程，松弛操作的時候也不再是加法，而是乘法，只有大于當前所記錄的概率的時候才會更新。

代碼如下：

class Solution {
public:class myless{public:bool operator()(const pair<int,double>&p1 , const pair<int,double>&p2){return p1.second < p2.second;}};double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {vector<double> dis(n,2.0); //我們使用一個大于1的概率作為默認值，表示不可達vector<vector<pair<int,double>>> g(n);for(int i = 0 ; i < edges.size() ; ++i){g[edges[i][0]].push_back(make_pair(edges[i][1],succProb[i]));g[edges[i][1]].push_back(make_pair(edges[i][0],succProb[i]));} priority_queue<pair<int,double>,vector<pair<int,double>>,myless> pq;dis[start_node] = 1.0;pq.push(make_pair(start_node,1.0));while(!pq.empty()){auto p = pq.top();if(p.first == end_node) return p.second;pq.pop();if(p.second < dis[p.first]) continue; //不是通往該點的最大概率//是通往該點的最大概率，那么需要松弛操作for(auto& p1 : g[p.first]){//對 p.first 的鄰點 p1 進行松弛操作if(dis[p1.first] > 1.0 || p.second * p1.second > dis[p1.first]){  //發現更大概率的路徑dis[p1.first] = p.second * p1.second;pq.push(make_pair(p1.first,dis[p1.first]));}} }return 0;}
};

7 最小體力消耗路徑?

1631. 最小體力消耗路徑 - 力扣（LeetCode）

題目解析：本題是一個求最短路徑的題目，但是本題對于路徑的定義不是路徑上所有邊的權值之和，而是所有的邊的權值的最大值，所以我們在更新路徑的時候換一種更新方式就行了。本題與到達最后一個房間的最少時間是同一類問題，二維空間的移動。

代碼如下：

class Solution {
public:class mygreater{public:bool operator()(const vector<int>& v1 , const vector<int>& v2){return v1[2] > v2[2];}};const int INF = 0x3f3f3f3f;int minimumEffortPath(vector<vector<int>>& heights) {int m = heights.size() , n = heights[0].size();vector<vector<int>> dis(m,vector<int>(n,INF));priority_queue<vector<int>,vector<vector<int>>,mygreater> pq;dis[0][0] = 0;pq.push({0,0,0});while(!pq.empty()){auto v = pq.top();pq.pop();if(v[2] > dis[v[0]][v[1]]) continue; //不是第一次出堆//第一次出堆，更新 (v[0],v[1]) 的最短路徑，進行松弛操作int x = v[0] , y = v[1] , mindis = v[2];if(x == m-1 && y == n-1) return mindis;if(x > 0 && (dis[x-1][y] == INF || dis[x-1][y] > max(mindis , abs(heights[x][y] - heights[x-1][y])))){ //更新 dis[x-1][y]dis[x-1][y] = max(mindis,abs(heights[x][y] - heights[x-1][y]));pq.push({x-1,y,dis[x-1][y]});}if(y > 0 && (dis[x][y-1] == INF || dis[x][y-1] > max(mindis , abs(heights[x][y] - heights[x][y-1])))){ //更新 dis[x][y-1]dis[x][y-1] = max(mindis,abs(heights[x][y] - heights[x][y-1]));pq.push({x,y-1,dis[x][y-1]});}if(x + 1 < m && (dis[x+1][y] == INF || dis[x+1][y] > max(mindis , abs(heights[x][y] - heights[x+1][y])))){ //更新 dis[x+1][y]dis[x+1][y] = max(mindis,abs(heights[x][y] - heights[x+1][y]));pq.push({x+1,y,dis[x+1][y]});}if(y + 1 < n && (dis[x][y+1] == INF || dis[x][y+1] > max(mindis , abs(heights[x][y] - heights[x][y+1])))){ //更新 dis[x][y]dis[x][y+1] = max(mindis,abs(heights[x][y] - heights[x][y+1]));pq.push({x,y+1,dis[x][y+1]});}}return dis[m-1][n-1];}
};

8 從第一個節點出發到最后一個節點的受限路徑數

1786. 從第一個節點出發到最后一個節點的受限路徑數 - 力扣（LeetCode）

題目解析：本題給定n個節點，編號從1開始，要求我們求出從1到n的受限路徑的數量。

受限路徑的定義：對于一條路徑，有多個節點以及相鄰節點連接的邊構成，假設節點序列為 (1,N2,N3...Nk,Nk+1...n)，那么這些節點必須要滿足一個特性，我們需要知道從節點 n 到其中每一個節點Ni的最短路徑 dis[i] ,那么需要滿足 :? dis[1] > dis[N2] > dis[N3] > dis[N4] > ... >dis[Nk] > dis[Nk+1]...>dis[n]，也就是每個節點到n的最短路徑都需要比路徑中下一個節點到節點n的最短路徑長。

那么不管怎么說，我們都需要先求出從節點n到其他所有結點的最短路徑dis[i]，這一步我們可以使用Dijkstra來完成。

class Solution {
public:class mygreater{public:bool operator()(const vector<int>& v1 , const vector<int>&v2){return v1[1] > v2[1];}};const int INF = 0x3f3f3f3f;int countRestrictedPaths(int n, vector<vector<int>>& edges) {vector<int> dis(n+1,INF);vector<vector<vector<int>>> gout(n+1); //出邊鄰接表，用于計算最短路徑vector<vector<int>> gin(n+1);  //入邊鄰接表，只需要保存邊，不需要保存邊的權重for(auto&v:edges){gout[v[0]].push_back({v[1],v[2]});gout[v[1]].push_back({v[0],v[2]});gin[v[0]].push_back(v[1]); //v[0]有一條入邊，起點為v[1]gin[v[1]].push)back(v[0]); //v[1]有一條出邊，起點為v[0]}//Dijkstra求最短路徑dis[n] = 0;priority_queue<vector<int>,vector<vector<int>>,mygreater> pq;pq.push({n,0});while(!pq.empty()){auto v = pq.top();pq.pop();if(v[1] > dis[v[0]]) continue;for(auto& v1 : g[v[0]]){if(dis[v1[0]] == INF || dis[v1[0]] > v1[1] + v[1]){dis[v1[0]] = v1[1] + v[1];pq.push({v1[0],dis[v1[0]]});}}}//走到這里就把從節點n到所有的點的最短路徑求出來保存在了 dis[i]中}
};

那么接下來我們就需要求出從節點 1 到節點 n 的受限路徑的個數，由于從節點1到節點n有很多的路徑可以到達，我們可以將這些路徑拆分為兩部分，先從節點 1 到節點 X,需要滿足節點1到節點 X有一條邊，同時 dis[1] > dis[X] ，然后另一部分就是從節點X到達節點n的一條受限路徑，那么我們的問題就轉換為了求節點X到節點n的受限路徑的個數。

那么我們可以使用動態規劃來解決這個問題：

dp[i] 表示從節點 i 到節點 n 的受限路徑的數量

狀態轉移方程推導：

對于dp[i]，從節點i到節點n的受限路徑的數量，我們需要拆分成兩部分，首先從節點i到達節點X，要求這條路徑是受限路徑，也就是 dis[i] > dis[X] ，然后再從X到節點n，這一條路徑也必須是受限路徑，那么從i到X再到n的受限路徑的個數就是 dp[X]。

$dp[i] =\sum_{1}^{n}(dp[X]) //(i->X , dis[i] > dis[X])$

但是可能有多個X滿足從i到X是受限路徑，從X到n有受限路徑，那么我們需要保證在填寫dp[i]的時候，所有的滿足條件的dp[X]都需要已經填完。這時候我們就可以思考一下，由于X必須要滿足dis[X] < dis[i]，那么意味著當填到 dp[i] 的時候，所有的dis[X]<dis[i] 的位置都需要已經填完，那么我們的填表順序就是按照 dis[i] 的大小，從小到大填表。

為了保證這個填表順序，我們可以使用一個堆來保存 dis[i] 和 i ，然后依次取出對堆頂元素，按照dis[i]的從小到大填寫 dp[i]。

細節問題：

初始化：需要初始化 dp[n] = 1

填表順序：按照dis[i]的從小到大，依次填寫 dp[i]

返回值：dp[1]

代碼如下：

class Solution {
public:class mygreater{public:bool operator()(const vector<int>& v1 , const vector<int>&v2){return v1[1] > v2[1];}};const int INF = 0x3f3f3f3f;const int MOD = 1e9+7;int countRestrictedPaths(int n, vector<vector<int>>& edges) {vector<int> dis(n+1,INF);vector<vector<vector<int>>> gout(n+1); //出邊鄰接表for(auto&v:edges){gout[v[0]].push_back({v[1],v[2]});gout[v[1]].push_back({v[0],v[2]});}//Dijkstra求最短路徑dis[n] = 0;priority_queue<vector<int>,vector<vector<int>>,mygreater> pq;pq.push({n,0});while(!pq.empty()){auto v = pq.top();pq.pop();if(v[1] > dis[v[0]]) continue;for(auto& v1 : gout[v[0]]){if(dis[v1[0]] == INF || dis[v1[0]] > v1[1] + v[1]){dis[v1[0]] = v1[1] + v[1];pq.push({v1[0],dis[v1[0]]});}}}//走到這里就把從節點n到所有的點的最短路徑求出來保存在了 dis[i]中vector<long long> dp(n+1 , 0) ; //dp[i]表示從節點i到節點n的受限路徑數量dp[n] = 1; ////按照 dis[i] 的升序來填寫dp[i]for(int i = 1 ; i < n ; ++i){pq.push({i,dis[i]});}while(!pq.empty()){auto v = pq.top();pq.pop();int i = v[0];//填寫dp[i]，看i有多少出邊，以及與出邊是否滿足受限路徑for(auto& v1: gout[i]){if(dis[i] > dis[v1[0]]) dp[i] = (dp[i] + dp[v1[0]]) % MOD;}if(i == 1) break;}return dp[1];}
};

9 最短路徑中的邊

3123. 最短路徑中的邊 - 力扣（LeetCode）

解析題目：題目給定m條邊，我們需要求出節點0到節點n-1的所有最短路徑中所用到過的邊，返回一個數組用于表示edges中的那那些邊被用到了，哪些沒被用到。

判斷每一條邊是否為某個點最短路徑的一條邊，我們需要在Dijkstra的過程中進行操作。對于每一個節點的最短路徑，比如dis[i] ，我們可以分成兩部分來看，最短路徑中最后一條邊為 j -> i ，那么最短路徑其實就是從起點到j的最短路徑，然后再加上 j->i 這一條邊，就組成了從起點到節點i的最短路徑。

我們可以理解為：從起點到任意一個節點 i 的最短路徑，一定是從起點到某一個節j點的最短路徑，再加上節點 j 到節點 i 的邊。

那么我們是不是可以理解為： 每新增一個節點，那么最短路徑的邊就會多出一條。

那么對于每個節點的最短路徑，我們是不是可以額外保存一個東西，就是他的最短路徑中的最后一條邊，這樣一來，我們在計算完所有的節點的最短路徑之后，就能知道所有的最短路徑的最后一條邊，也就是所有的組成最短路徑的邊，只有這些邊是在最短路徑中的，其他的邊都不在最短路徑中。

那么我們在Dijkstra的過程中，更新的dis[i]的時候，還需要更新dis[i]的最后一條邊，我們可以使用一個數組 vector<vector<int>> use 來記錄，use[i] 存儲的是dis[i]的最后一條邊在 edges 的下標,因為可能存在多條最短路徑，所以可能有多條邊需要存儲。

那么use數組就能保存所有點的最短路徑的最后一條邊。

但是題目要求的是從節點0到節點n-1的所有最短路徑中的所有邊，那么n-1的所有最短路徑，不管怎么樣，都可以拆分為前一個點到n-1的邊以及前一個點的最短邊。

可能多條最短路徑，那么n-1的前一個點可能是一個，也可能有多個都可以通過最短路徑到n-1，那么我們只需要記錄一下上一個點。

那么我們在使用一個數組vector<vector<int>>? prev , prev[i] 是一個一維數組，用于保存從起點的節點i的所有最短路徑中，倒數第二個節點編號。

那么后續我們就能夠根據 prev[n-1] 來到倒退出所有最短路徑所經過的所有的節點，而到這些節點所需要的邊能夠在use數組中找到，那么就能夠完成本題。

當然其實還可以繼續優化，因為use數組和prev數組在功能上有重復，其實最終可以刪除其中一個數組，但是其實思路不會有太大變化，所以我們這里也不進行優化了。

代碼如下：

class Solution {
public:class mygreater{public:bool operator()(const vector<int>& v1 , const vector<int>&v2){return v1[1] > v2[1];}    };const int INF = 0x3f3f3f3f;void dfs(const vector<vector<int>>&prev,int end , unordered_set<int>&nodes){if(nodes.find(end) != nodes.end()) return;nodes.insert(end);cout<<"dfs:end="<<end<<endl;for(auto e : prev[end]){if(nodes.find(e) != nodes.end())continue;dfs(prev,e,nodes);}}vector<bool> findAnswer(int n, vector<vector<int>>& edges) {vector<int> dis(n,INF);vector<vector<int>> prev(n); //記錄每個節點的所有最短路徑的倒數第二個節點vector<vector<vector<int>>> g(n);  //g[i] 保存的是從節點i的出邊，是一個一維數組vector,{x,y,z} x是目的節點，y是邊的權值，z是邊在edges的下標for(int i = 0 ; i < edges.size() ; ++i){g[edges[i][0]].push_back({edges[i][1],edges[i][2],i});g[edges[i][1]].push_back({edges[i][0],edges[i][2],i});}vector<vector<int>> use(n);  //use[i] 存儲 dis[i] 的下標,有的dis[i] 不可達或者用不上，那么use[i] = -1,最后一條邊也有可能有多個priority_queue<vector<int>,vector<vector<int>>,mygreater> pq;dis[0] = 0 ;pq.push({0,0});while(!pq.empty()){auto v = pq.top();pq.pop();if(v[0] == n - 1) break; //后續所有的最短路徑都大于等于 dis[n-1]，就算能到n-1，也不是最短路徑了if(v[1] > dis[v[0]]) continue; //非最短路徑出堆//對 v[0] 的鄰點進行松弛操作for(auto& v1 : g[v[0]]){if(dis[v1[0]] == INF || dis[v1[0]] > v[1] + v1[1]){ //找到更小路徑，那么之前記錄的prev[v1[0]]無效了dis[v1[0]] = v[1] + v1[1];use[v1[0]].clear();use[v1[0]].push_back(v1[2]);prev[v1[0]].clear();prev[v1[0]].push_back(v[0]); //本條最短路徑的倒數第二個節點為 v[0]pq.push({v1[0],dis[v1[0]]});}else if(dis[v1[0]] == v[1] + v1[1]) {prev[v1[0]].push_back(v[0]);use[v1[0]].push_back(v1[2]);}}}//然后我們需要求出所有最短路徑所經過的節點//為了去重，我么可以使用 unordered_set 來存儲cout<<"---"<<endl;for(auto e : prev[n-1]) cout<<e<<endl;unordered_set<int> nodes;//對于 prev[n-1],可能有多個節點的最短路徑加上該節點到n-1的邊是相等的最短路徑，所以我們需要遍歷//由于需要大量的循環來判斷，我們直接用遞歸來解決dfs(prev,n-1,nodes);vector<bool> ans(edges.size(),false);for(auto e : nodes){ //用到的所有節點for(auto i : use[e]){ans[i] = true;}}return ans;}
};

10 到達目的地的方案數

1976. 到達目的地的方案數 - 力扣（LeetCode）

解析題目：本題要求我們求出從節點0到節點n-1的最短路徑的條數，這個題其實相對于上一個題比較簡單，因為上一個題我們需要統計所有的最短路徑的所有的節點，而這個題中我們只需要統計最短路徑的條數。

類似的，假設其中有一條從0到n-1的最短路徑的倒數第二個節點為 X ，而從X到n-1只有一條路，這一條路徑長度是固定的，那么這條最短路徑其實就是先從節點 0 到節點X的最短路徑，再加上這一條邊，那么就構成了從0到n-1的最短路徑，那么經過X的最短路徑有多少條，就取決于從0到n-1的最短路徑有多少條。

那么這樣一來，我們在更新每一個節點的最短路徑dis[i]的時候，不僅需要記錄最短路徑的數值，還需要記錄最短路徑出現的次數，需要使用一個cnt數組來記錄。

當我們使用其他節點對節點 i 進行松弛操作的時候，如果更新出了最短路徑, mindis + g(x->i) < dis[i]，那么此時是一條全新的最短路徑，需要更新cnt[i] = cnt[x] ; 如果mindis + g(x->i) == dis[i] ，那么說明這一條路徑也是從0到節點 i 的最短路徑，那么需要對 cnt[i] += cnt[x];

最終當0到節點 n-1 的最短路徑出堆的時候，我們就確定了一共有多少條最短路徑，cnt[n-1]，因為最短路徑的確定其實在出堆之前就已經統計完了，不管是 dis[n-1] 還是 cnt[n-1]。

那么代碼如下：

class Solution {
public:const int MOD = 1e9+7;const int INF = 0x3f3f3f3f;class mygreater{public:bool operator()(const vector<long long>& v1 , const vector<long long>& v2){return v1[1] > v2[1];}};int countPaths(int n, vector<vector<int>>& roads) {vector<long long> dis(n,INF);vector<vector<vector<int>>>g(n);for(auto&v:roads){g[v[0]].push_back({v[1],v[2]});g[v[1]].push_back({v[0],v[2]});}vector<long long>cnt(n,0);priority_queue<vector<long long>,vector<vector<long long>>,mygreater> pq;dis[0] = 0;cnt[0] = 1;pq.push({0,0});while(!pq.empty()){auto v = pq.top();pq.pop();if(v[1] > dis[v[0]]) continue;if(v[0] == n-1) break;for(auto& v1 : g[v[0]]){if(dis[v1[0]] == INF || dis[v1[0]] > v[1] + v1[1]){dis[v1[0]] = v[1] + v1[1];cnt[v1[0]] = cnt[v[0]];pq.push({v1[0],dis[v1[0]]});}else if(dis[v1[0]] == v[1] + v1[1]) cnt[v1[0]] = (cnt[v1[0]] + cnt[v[0]])%MOD;}}return cnt[n-1];}
};

11 水位上升的泳池中游泳

778. 水位上升的泳池中游泳 - 力扣（LeetCode）

題目解析：本題其實類似于到達最后一個房間的最少時間，每個方格都有最早可到達時間的限制，只有時間大于等于平臺高度時才能到達本方格。

轉換一下問題：我們需要找到一條路徑，路徑所經過的所有方格中，最大的方格的高度就是本條路徑所需要的時間。那么我們需要找到一條節點數值最小的路徑。

我們假設從節點 0 走到節點 x 所需的最少時間是 t1 ，t1其實就是代表從 0 到 x 的最短耗時路徑中，高度最大的方格的高度，那么從 x 再走到 y ，如果y的高度是 t2 ，那么從 0 到 x 的所需要的時間就是 min(t1,t2)。

代碼如下：

class Solution {
public:const int INF = 0X3f3f3f3f;class mygreater{public:bool operator()(const vector<int>& v1 , const vector<int>& v2){return v1[2] > v2[2];}};int swimInWater(vector<vector<int>>& grid) {int n = grid.size();vector<vector<int>> dis(n,vector<int>(n,INF));dis[0][0] = grid[0][0];priority_queue<vector<int>,vector<vector<int>>,mygreater> pq;pq.push({0,0,dis[0][0]});while(!pq.empty()){auto v = pq.top();pq.pop();if(v[2] > dis[v[0]][v[1]]) continue;if(v[0] == v[1] && v[1] == n - 1) return v[2];//松弛操作，更新隔壁四個點最少時間int x = v[0] , y = v[1] , mindis = v[2]; if(x > 0 && (dis[x-1][y] == INF || dis[x-1][y] > max(mindis , grid[x-1][y]))){dis[x-1][y] = max(mindis , grid[x-1][y]);pq.push({x-1,y,dis[x-1][y]});}if(y > 0 && (dis[x][y-1] == INF || dis[x][y-1] > max(mindis , grid[x][y-1]))){dis[x][y-1] = max(mindis , grid[x][y-1]);pq.push({x,y-1,dis[x][y-1]});}if(x + 1 < n && (dis[x+1][y] == INF || dis[x+1][y] > max(mindis , grid[x+1][y]))){dis[x+1][y] = max(mindis , grid[x+1][y]);pq.push({x+1,y,dis[x+1][y]});}if(y + 1 < n && (dis[x][y+1] == INF || dis[x][y+1] > max(mindis , grid[x][y+1]))){dis[x][y+1] = max(mindis , grid[x][y+1]);pq.push({x,y+1,dis[x][y+1]});}}return dis[n-1][n-1];}
};

12 前往目標的最小代價

2662. 前往目標的最小代價 - 力扣（LeetCode）

解析題目：本題提供了兩種路徑，一種是直接從 {x1,y1} 走到 {x1,y2}，此時需要的代價是 |x1-x2| + |y1-y1| ，另一種是通過頁數路徑，也就是題目給定的路徑來走，代價則是指定的代價。

由于第一種走法會導致從一個點可以直接走到地圖中的任意一個點，這樣就會導致我們難以枚舉這些路徑，或者說枚舉這些路徑的復雜度過大，每一個點的路徑就相當于有 m*n?條。但是其實第一種走法是可以轉換一下：

每一次只走一格，也就是上下左右四個方向中選一個走，代價為1，滿足 |x1-x2| + |y1-y2|，而從本節點到任意節點的直接的走法，其實可以看成是一步一步走過去的，每一次就走一格，那么本題的走法我們就可以替換一下：

1、走到上下左右四個鄰格，代價為1

2、特殊路徑，起點終點以及代價由題目指定。

那么接下來就是一個簡單的Dijkstra的過程了。

但是我么可以注意一下題目的范圍 : 起點和終點的橫縱坐標范圍 10^5 ，也就是十萬，如果暴力Dijkstra的話，極有可能會超時，以及空間會溢出，那么我們不能直接進行暴力的dijkstra求解最短路徑。

其實我們并不需要用到這么多的點，因為哪些沒有特殊路徑的點我們只能通過第一種方法到達，并不需要關注具體的最短路徑，我們需要額外關注的是地圖中的特殊路徑，這樣一來，我們其實可以首先將特殊路徑的所有節點看成是一個圖的節點，也就是一個建圖過程。圖中所有的節點都是相互連通的，可以通過第一種方法到達。

那么建圖如何表示這些坐標呢？

由于所有的二維空間的坐標二元組都是 {x(int),y(int)}，橫縱坐標都是32位的，那么我們是不是可以直接用一個64位的整數來表示一個這樣的二元組，我們使用 long long index = x << 32 + y ，來標識二維空間中的 {x,y} ，這個過程是可逆的，我們可以通過 64 位的一維位置逆轉乘二元組。

我們可以為每一個節點進行編號，從0開始到n，使用數組來保存節點編號與其位置的關系，這一步需要使用哈希表去重。我們是在遍歷特殊路徑的時候來為節點編號的，在遍歷的時候可以將鄰接表也填好。

建圖：無非就是為所有的邊的兩端節點進行編號，為了去重，我們需要使用一個哈希表來保存節點位置和節點編號的映射關系。

    int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {int x = specialRoads.size() * 2 + 2;  //最多x個節點vector<long long> nodes(x);unordered_map<long long , int> hash; //對節點進行去重vector<vector<vector<int>>> g(x); //鄰接表int n = 1; //記錄節點總數nodes[0] = ((long long)start[0] << 32) + start[1];  //起點編號為 0 hash[nodes[0]] = 0; //保存0節點for(auto& v : specialRoads){long long x1 = v[0] , y1 = v[1] , x2 = v[2] , y2 = v[3] ;int w = v[4];long long n1 = (x1<<32) + y1 , n2 = (x2 << 32) + y2;//判斷兩個節點是否已經存在，找節點編號int index1 = 0 , index2 = 0;if(hash.find(n1) == hash.end()){hash[n1] = n;nodes[n] = n1;index1 = n++;}else index1 = hash[n1];if(hash.find(n2) == hash.end()){hash[n2] = n;nodes[n] = n2;index2 = n++;}else index2 = hash[n2];//兩個節點編號分別為 index1 和 index2//維護鄰接表g[index1].push_back({index2,w});// g[index2].push_back({index1,w});  //注意邊是單向邊}//n為節點總數//然后還需要將終點記錄long long end = ((long long)target[0] << 32) + target[1];if(hash.find(end) == hash.end()){nodes[n] = end;hash[end] = n;n++;}int targetnode = hash[end]; //記錄終點的節點編號，便于提前返回

然后就是使用Dijkstra算法求最短路徑，但是注意我們的終點的編號不一定是n-1，所以我們需要保存終點的節點編號。

Dijkstra的過程和我們的模板大差不差，只不過除了我們所記錄的邊之外，所有的節點兩兩之間都可以看作還有一條邊，就是移動方法1的邊，這些邊我們也需要進行松弛操作。

全部代碼如下：

class Solution {
public:const int INF = 0x3f3f3f3f;class mygreater{public:bool operator()(const vector<int>& v1 , const vector<int>& v2){return v1[1] > v2[1];}};int getdistance(long long n1 , long long n2){int x1 = n1>>32 , y1 = n1 & 0xffffffff , x2 = n2>>32 , y2 = n2 & 0xffffffff;return abs(x1-x2) + abs(y1-y2); }int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {int x = specialRoads.size() * 2 + 2;  //最多x個節點vector<long long> nodes(x);unordered_map<long long , int> hash; //對節點進行去重vector<vector<vector<int>>> g(x); //鄰接表int n = 1; //記錄節點總數nodes[0] = ((long long)start[0] << 32) + start[1];  //起點編號為 0 hash[nodes[0]] = 0; //保存0節點for(auto& v : specialRoads){long long x1 = v[0] , y1 = v[1] , x2 = v[2] , y2 = v[3] ;int w = v[4];long long n1 = (x1<<32) + y1 , n2 = (x2 << 32) + y2;//判斷兩個節點是否已經存在，找節點編號int index1 = 0 , index2 = 0;if(hash.find(n1) == hash.end()){hash[n1] = n;nodes[n] = n1;index1 = n++;}else index1 = hash[n1];if(hash.find(n2) == hash.end()){hash[n2] = n;nodes[n] = n2;index2 = n++;}else index2 = hash[n2];//兩個節點編號分別為 index1 和 index2//維護鄰接表g[index1].push_back({index2,w});// g[index2].push_back({index1,w});  //注意邊是單向邊}//n為節點總數//然后還需要將終點記錄long long end = ((long long)target[0] << 32) + target[1];if(hash.find(end) == hash.end()){nodes[n] = end;hash[end] = n;n++;}int targetnode = hash[end]; //記錄終點的節點編號，便于提前返回// cout<<n<<endl;//接下來做Dijkstrapriority_queue<vector<int>,vector<vector<int>>,mygreater> pq;vector<int> dis(n,INF);vector<bool> flag(n,false);  //標識每個節點是否已經確定最小路徑dis[0] = 0;pq.push({0,0});while(!pq.empty()){auto v = pq.top();pq.pop();if(v[1] > dis[v[0]]) continue; //不是最小路徑if(v[0] == targetnode) return v[1];  //注意不是到 n-1 的最短路徑，目標節點可能由于去重的原因，在添加邊的節點的時候就添加進去了//走到這里說明是最小路徑最小路徑//那么可以標記 flag[v[0]]flag[v[0]] = true;//松弛操作,有兩種路徑，一種是直接走，這一種可以從節點v[0]到達其他所有的節點，我們可以嘗試這種方法看能否更新出其他節點的更小路徑for(int i = 0 ; i < n ; ++i){if(!flag[i] && (dis[i] == INF || v[1] + getdistance(nodes[v[0]],nodes[i]) < dis[i])){dis[i] = v[1] + getdistance(nodes[v[0]] , nodes[i]);pq.push({i,dis[i]});}} //然后再嘗試特殊路徑的點的更新for(auto&v1: g[v[0]]){if(!flag[v1[0]] && (dis[v1[0]] == INF || v[1] + v1[1] < dis[v1[0]])){dis[v1[0]] = v[1] + v1[1];pq.push({v1[0] , dis[v1[0]]});}}}return getdistance(nodes[n-1] , nodes[0]);}
};

啟示

對于這類型圖中的節點十分多，大部分節點之間的路徑是一個可預測的長度，而有一些特殊路徑的長度有題目給出，那么我們就可以嘗試先建圖，再去思考使用上面算法來求解最短路徑的問題。

13 使兩個整數相等的數位操作

3377. 使兩個整數相等的數位操作 - 力扣（LeetCode）

題目解析：題目意思很簡單，給定兩個數位個數相同的整數 m 和 n ，要求我們將m轉換為 n，只能對m某個數位進行+1或者-1，返回最少的操作代價，總的操作代價就是在轉換過程中的所有的值的總和，要求在中間過程中n不能是質數。

本題怎么使用Dijkstra來完成呢？

因為題目限制 m 和 n 都是小于10000的，把和 m 數位個數相同的所有整數看成是圖的節點，最多也就是 9000 個節點，而每一個節點(除了質數)都有邊連接向進行一次數位操作能夠相同的節點，邊的權值為1。當然其實并沒有

但是題目還有一個要求就是不能對 9 加一也不能對 0減一。

本題還要求轉換過程中不能是質數，所以我們需要標識一下所有的質數。

質數的篩法常用的有兩種：埃式篩和歐拉篩，這里我們直接使用歐拉篩來完成，在全局使用lambda表達式來進行篩選。

    bool flag[10001] ={false};int init =[&]{flag[1] = true;  //為true表示是質數，否則為合數for(int i = 2  ; i < 10000; ++i){if(!flag[i]){for(int j = i * i ; j < 10001 ; j += i) flag[j] = true;  //j為合數，j = i * (i + x)}}return 0;}();

然后我們就需要完成Dijkstra的過程，起點無非就是n，n所需的數位操作代價為n自身，然后不斷根據出堆的數據x的操作代價，來更新x的鄰節點，也就是x經過一次數位操作能夠轉換的數據。

題目還有一個很大的坑，就是在轉換過程中，位數不能減少，也就是如果是第一位為1，我們其實不能將其減到0，這一點題目中似乎沒有說明。

代碼如下：


class Solution {
public:bool flag[10001] ={false};int init =[&]{//為true表示是合數，否則為質數flag[1] = true;for(int i = 2  ; i <= 10000; ++i){if(!flag[i]){for(int j = i * i ; j < 10001 ; j += i) flag[j] = true;  //j為合數，j = i * (i + x)}}return 0;}();class mygreater{public:bool operator()(const vector<int>& v1 , const vector<int>& v2){return v1[1] > v2[1];}};const int INF = 0x3f3f3f3f;int minOperations(int n, int m) {if(!flag[m]) return -1; //質數不可達vector<int> dis(10001,INF);dis[n] = n;int len = 0 ; //求n的位數，方便后續操作 int n1 = n;while(n1){n1/=10;len ++;  }priority_queue<vector<int>,vector<vector<int>> ,mygreater>pq;pq.push({n,n});while(!pq.empty()){auto v = pq.top();pq.pop();int x = v[0] , cost = v[1];if(x == m) return cost; //提前返回if(!flag[x]) continue; //x是質數的話不可達if(cost > dis[x]) continue; //不是第一次出堆//然后開始進行加一和減一的操作 //取出x的每一個數位int prevnum = x , backnum = 0 ; //將數字分成兩部分看，對前部分加一減一 *pow(10,i) ，然后加上后面一部分for(int i = 0 ; i < len ; ++i){if(prevnum % 10 < 9){ //前半部分可以進行加一操作int prev = prevnum + 1;int total = prev * pow(10,i) + backnum;  //組合成新的數if(flag[total] && dis[total] > cost + total){dis[total] = cost + total;pq.push({total,dis[total]});}}if(prevnum % 10 > 0){int prev = prevnum - 1;int total = prev * pow(10,i) + backnum;if(prev != 0){if(flag[total] && dis[total] > cost + total){dis[total] = cost + total;pq.push({total , dis[total]});}}}backnum += ((prevnum%10) * pow(10,i));prevnum /= 10;}}return -1;}
};