算法模板

Dijkstra題目代碼模板

樸素dijkstra算法

對應(yīng)模板題：Dijkstra求最短路 I
時間復雜是 O(n^2+m)：n 表示點數(shù)，m 表示邊數(shù)

int g[N][N];  // 存儲每條邊
int dist[N];  // 存儲1號點到每個點的最短距離
bool st[N];   // 存儲每個點的最短路是否已經(jīng)確定// 求1號點到n號點的最短路，如果不存在則返回-1
int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 0; i < n - 1; i ++ ){int t = -1;     // 在還未確定最短路的點中，尋找距離最小的點for (int j = 1; j <= n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;// 用t更新其他點的距離for (int j = 1; j <= n; j ++ )dist[j] = min(dist[j], dist[t] + g[t][j]);st[t] = true;}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}

堆優(yōu)化版dijkstra

對應(yīng)模板題：Dijkstra求最短路 II
時間復雜度 O(mlogn)：n 表示點數(shù)，m 表示邊數(shù)

typedef pair<int, int> PII;int n;      // 點的數(shù)量
int h[N], w[N], e[N], ne[N], idx;       // 鄰接表存儲所有邊
int dist[N];        // 存儲所有點到1號點的距離
bool st[N];     // 存儲每個點的最短距離是否已確定// 求1號點到n號點的最短距離，如果不存在，則返回-1
int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 1});      // first存儲距離，second存儲節(jié)點編號while (heap.size()){auto t = heap.top();heap.pop();int ver = t.second, distance = t.first;if (st[ver]) continue;st[ver] = true;for (int i = h[ver]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > distance + w[i]){dist[j] = distance + w[i];heap.push({dist[j], j});}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}

樹與圖的存儲

樹是一種特殊的圖，與圖的存儲方式相同。
對于無向圖中的邊ab，存儲兩條有向邊a->b, b->a。
因此我們可以只考慮有向圖的存儲。

(1) 鄰接矩陣：

g[a][b] 存儲邊a->b

(2) 鄰接表：

https://www.acwing.com/video/21/
（1:20:00左右）

// 對于每個點k，開一個單鏈表，存儲k所有可以走到的點。h[k]存儲這個單鏈表的頭結(jié)點
int h[N], e[N], ne[N], idx;// 添加一條邊a->b
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}int main(){...// 初始化idx = 0;memset(h, -1, sizeof h);...
}

有權(quán)重時模板：

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

關(guān)于e[],ne[],h[]的理解

h[N] : 表示 第 i 個節(jié)點的 第一條邊的 idx
ne[M] : 表示 與 第 idx 條邊 同起點 的 下一條邊 的 idx
e[M] : 表示 第idx 條邊的 終點

N ： 節(jié)點數(shù)量
M：邊的數(shù)量
i : 節(jié)點的下標索引
idx ： 邊的下標索引
變量初始化定義：

int h[N], e[M], ne[M], idx;

當我們加入一條邊的時候：

void add(int a,int b){e[idx] = b;      // 記錄 加入的邊 的終點節(jié)點ne[idx] = h[a]; // h[a] 表示 節(jié)點 a 為起點的第一條邊的下標，ne[idx] = h[a] 表示把 h[a] 這條邊接在了 idx 這條邊的后面，其實也就是把 a 節(jié)點的整條鏈表 接在了 idx 這條邊 后面；目的就是為了下一步 把 idx 這條邊 當成 a 節(jié)點的單鏈表的 第一條邊，完成把最新的一條邊插入到 鏈表頭的操作；h[a] = idx++; // a節(jié)點開頭的第一條邊置為當前邊，idx移動到下一條邊
}

要注意的是鄰接表插入新節(jié)點時使用的是“頭插”，如圖中節(jié)點2：當插入2 1時此時為2—>1, 而后插入2 4后，此時為 2—> 4 —> 1.

關(guān)于堆的原理與操作

二、數(shù)據(jù)結(jié)構(gòu)10：堆 模板題+算法模板（堆排序，模擬堆）

模板題

Dijkstra求最短路 I

原題鏈接

https://www.acwing.com/problem/content/851/

題目

給定一個 n
個點 m
條邊的有向圖，圖中可能存在重邊和自環(huán)，所有邊權(quán)均為正值。

請你求出 1
號點到 n
號點的最短距離，如果無法從 1
號點走到 n
號點，則輸出 ?1
。

輸入格式
第一行包含整數(shù) n
和 m
。

接下來 m
行每行包含三個整數(shù) x,y,z
，表示存在一條從點 x
到點 y
的有向邊，邊長為 z
。

輸出格式
輸出一個整數(shù)，表示 1
號點到 n
號點的最短距離。

如果路徑不存在，則輸出 ?1
。

數(shù)據(jù)范圍
1≤n≤500
,
1≤m≤105
,
圖中涉及邊長均不超過10000。

輸入樣例：

3 3
1 2 2
2 3 1
1 3 4

輸出樣例：

3

思路

題解

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
const int M = 1e5 + 10;
int dist[N]; // 存各點與1號點的最短距離 
bool st[N]; // 存各點是否已被 處理為最短距離點 判斷 (當前已確定最短距離的點) 
int g[N][N];
int n,m,t;int dijkstra(){memset(dist,0x3f,sizeof dist);dist[1] = 0;for(int i = 0;i<n;i++){t = -1; //	t: 不在 當前已確定最短距離的點 中的距離最短的點 初始化為-1 for(int j = 1;j<=n;j++){if(!st[j] && (t == -1 || dist[t] > dist[j])){t = j;}}st[t] = true;for(int j=1;j<=n;j++){dist[j] = min(dist[j],dist[t] + g[t][j]); //用（1到t+t到j(luò)）的長度與（1到j(luò)）的長度進行對比更新 }}if(dist[n] == 0x3f3f3f3f) return -1;else return dist[n];
}
int main(){cin>>n>>m;memset(g,0x3f,sizeof g);for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;g[x][y] = min(g[x][y],z);}	int res = dijkstra();printf("%d",res);return 0;}

Dijkstra求最短路 II

原題鏈接

https://www.acwing.com/problem/content/852/

題目

給定一個 n
個點 m
條邊的有向圖，圖中可能存在重邊和自環(huán)，所有邊權(quán)均為非負值。

請你求出 1
號點到 n
號點的最短距離，如果無法從 1
號點走到 n
號點，則輸出 ?1
。

輸入格式
第一行包含整數(shù) n
和 m
。

接下來 m
行每行包含三個整數(shù) x,y,z
，表示存在一條從點 x
到點 y
的有向邊，邊長為 z
。

輸出格式
輸出一個整數(shù)，表示 1
號點到 n
號點的最短距離。

如果路徑不存在，則輸出 ?1
。

數(shù)據(jù)范圍
1≤n,m≤1.5×105
,
圖中涉及邊長均不小于 0
，且不超過 10000
。
數(shù)據(jù)保證：如果最短路存在，則最短路的長度不超過 109
。

輸入樣例：

3 3
1 2 2
2 3 1
1 3 4

輸出樣例：

3

思路

使用堆優(yōu)化，選擇用stl中的priority_queue進行操作

關(guān)于st[N]數(shù)組 處理冗余部分
https://www.acwing.com/solution/content/167860/

題解

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int M = 2e5 + 10;
typedef pair<int,int> PII;
int dist[N]; // 存各點與1號點的最短距離 
bool st[N]; // 存各點是否已被 處理為最短距離點 判斷 (當前已確定最短距離的點) 
//int g[N][N];
//堆優(yōu)化中，由于為稀疏圖，因此使用鄰接表進行存儲
int h[N],w[N],e[N],ne[N],idx; int n,m,t;//鄰接表插入處理 
void add(int a,int b,int c){e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}int dijkstra(){memset(dist,0x3f,sizeof dist);dist[1] = 0;//	堆優(yōu)化版dijkstrapriority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({0,1}); // {距離，編號}編號為1的點距離為0，表示1到1的距離為0 while(heap.size()){auto t = heap.top();heap.pop();int ver = t.second, distance = t.first; // distance :結(jié)點1到結(jié)點ver的距離if(st[ver]) continue;  // 冗余的話跳過st[ver] = true;for(int i=h[ver]; i!=-1; i=ne[i]){ // 鄰接表遍歷,從h[ver]開始遍歷可達的所有結(jié)點int j = e[i];//			w[i]:結(jié)點ver到結(jié)點j的距離if(dist[j]>distance + w[i]){ // 1--->i的距離 和 1--->ver--->i的距離相比dist[j] = distance + w[i]; heap.push({dist[j],j});}} }if(dist[n] == 0x3f3f3f3f) return -1;else return dist[n];
}
int main(){cin>>n>>m;
//	memset(g,0x3f,sizeof g);memset(h,-1,sizeof h);;for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;add(x,y,z);}	int res = dijkstra();printf("%d",res);return 0;}

1003 Emergency

原題鏈接

原題鏈接

題目

題目大意：n個城市m條路，每個城市有救援小組，所有的邊的邊權(quán)已知。給定起點和終點，求從起點到終點的最短路徑條數(shù)以及最短路徑上的救援小組數(shù)目之和。如果有多條就輸出點權(quán)（城市救援小組數(shù)目）最大的那個

思路

用一遍Dijkstra算法，救援小組個數(shù)相當于點權(quán)，用Dijkstra求邊權(quán)最小的最短路徑的條數(shù)，以及這些最短路徑中點權(quán)最大的值
dis[i]表示從出發(fā)點到i結(jié)點最短路徑的路徑長度，
num[i]表示從出發(fā)點到i結(jié)點最短路徑的條數(shù)，
w[i]表示從出發(fā)點到i點救援隊的數(shù)目之和
當判定dis[u] + e[u][v] < dis[v]的時候，
不僅僅要更新dis[v]，還要更新num[v] = num[u], w[v] = weight[v] + w[u];
如果dis[u] + e[u][v] == dis[v]，還要更新num[v] += num[u]，而且判斷一下是否權(quán)重w[v]更小，如果更小了就更新w[v] = weight[v] + w[u];

題解

基于上述樸素版dijkstra進行改進，

#include <bits/stdc++.h>
using namespace std;
//題目大意：n個城市m條路，每個城市有救援小組，所有的邊的邊權(quán)已知。給定起點和終點，求從起點到終點的最短路徑條數(shù)以及最短路徑上的救援小組數(shù)目之和。如果有多條就輸出點權(quán)（城市救援小組數(shù)目）最大的那個～
//
//分析：用一遍Dijkstra算法～救援小組個數(shù)相當于點權(quán)，用Dijkstra求邊權(quán)最小的最短路徑的條數(shù)，以及這些最短路徑中點權(quán)最大的值～dis[i]表示從出發(fā)點到i結(jié)點最短路徑的路徑長度，num[i]表示從出發(fā)點到i結(jié)點最短路徑的條數(shù)，w[i]表示從出發(fā)點到i點救援隊的數(shù)目之和～當判定dis[u] + e[u][v] < dis[v]的時候，不僅僅要更新dis[v]，還要更新num[v] = num[u], w[v] = weight[v] + w[u]; 如果dis[u] + e[u][v] == dis[v]，還要更新num[v] += num[u]，而且判斷一下是否權(quán)重w[v]更小，如果更小了就更新w[v] = weight[v] + w[u]; const int N = 510;
int g[N][N];
int c1,c2;
int dist[N]; //dist[i]表示從出發(fā)點到i結(jié)點最短路徑的路徑長度
int weight[N]; //每個城市救援隊數(shù)量
int w[N]; //w[i]表示從出發(fā)點到i點救援隊的數(shù)目之和
bool st[N]; 
int num[N]; //num[i]表示從出發(fā)點到i結(jié)點最短路徑的條數(shù)int n,m;void dij(){w[c1] = weight[c1];memset(dist,0x3f,sizeof dist);dist[c1] = 0;num[c1] = 1;int t;for(int i=0;i<n;i++){t = -1;for(int j=0;j<n;j++){if(!st[j] && (t==-1 || dist[t] >dist[j]) ){t = j;}}st[t] = true;for(int j=0;j<n;j++){
//			dist[j] = min(dist[j],dist[t] + g[t][j]);if(dist[j]>dist[t]+g[t][j]){ //當判定dis[u] + e[u][v] < dis[v]的時候，不僅僅要更新dis[v]，還要更新num[v] = num[u], w[v] = weight[v] + w[u]; dist[j] = dist[t]+g[t][j];num[j] = num[t];w[j] = w[t] + weight[j];  
//				cout<<t<<" "<<w[t]<<endl;
//				w[j]+=weight[t];}else if(dist[j]==dist[t]+g[t][j]){ //如果dis[u] + e[u][v] == dis[v]，還要更新num[v] += num[u]，而且判斷一下是否權(quán)重w[v]更小，如果更小了就更新w[v] = weight[v] + w[u]; num[j] = num[t]+num[j];if(w[t]+weight[j] > w[j]){w[j] = w[t] + weight[j];}}	}}//	return w[c2];	
}
int main(){cin>>n>>m>>c1>>c2;for(int i=0;i<n;i++){int t;cin>>t;weight[i] = t;}memset(g,0x3f,sizeof g); // 賦值無窮大 for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;g[x][y] = g[y][x] = z; // 無向圖！所以存雙向信息 }dij();cout<<num[c2]<<" "<<w[c2];
} 

參考鏈接：1003. Emergency (25)-PAT甲級真題（Dijkstra算法）